Re: [Boost-users] Equality comparison of boost::function<>

Subject: Re: [Boost-users] Equality comparison of boost::function<>
From: Christopher Jefferson (chris_at_[hidden])
Date: 2009-08-08 13:37:35

On 8 Aug 2009, at 17:45, Tobias Columbus wrote:

> Christopher Jefferson wrote:
>> On 8 Aug 2009, at 07:30, Scott McMurray wrote:
>>> 2009/8/7 Zachary Turner <divisortheory_at_[hidden]>:
>>>>
>>>> Out of curiosity, is it impossible due to technical limitations,  
>>>> or is
>>>> it just not implemented because it's either difficult or nobody's  
>>>> ever
>>>> gotten around to it?
>>>>
>>>
>>> Undecidable by reduction to the halting problem in general, though
>>> apparently possible for straight-line code (no loops/recursion)
>>> through the brute-force method of generate all paths and send them  
>>> to
>>> a theorem prover to prove equivalence.
>> That sounds very unnecessary. Surely it would be sufficient, and  
>> what most people would expect, to check if the two function objects  
>> point to the same function (in the sense of location in memory), as  
>> opposed to logically equivalent functions?
>> I wrote some code that compares instances of the SAT problem, of  
>> course I didn't do the NP-hard job of checking if they had the same  
>> set of solutions, just if they were actually the same problem.
>
>> Chris
>
> Comparing two SAT-instances actually is NP-hard, too.
> Given any SAT formula F, you could just check if (not F) is the same  
> problem as the trivial formula (true). If (not F) is equivalent to  
> (true), F is unsatisfiable and otherwise F is satisfiable.

As I thought I implied, I know comparing if two SAT instances have the  
same set of solutions is NP-hard. However when I wrote a comparison  
function, I considered (for example) the problems "X" and "X \/ (Y /\  
not Y)" to be different problems with the same set of solutions.

Similarly, I wouldn't expect an implementation of boost::function to  
say that, given:

int f() { return 2; } and int g() { return 2; }

to say that f and g are the same function, in the same way C++ would  
not say that f == g either.

But, this is very off-topic I think. Sorry.

Chris