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

Subject: Re: [Boost-users] Equality comparison of boost::function<>
From: Tobias Columbus (t.columbus_at_[hidden])
Date: 2009-08-08 20:37:35

Christopher Jefferson wrote:
> 
> 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.

Yes, you're right! I agree, that function-pointer comparison would 
suffice for some (many?) use-cases of boost::function, but actually I 
just wanted to point out that theoretical ( and off-topic! ) 
complication with formula-comparison. Sorry.

Tobi

> 
> Chris
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>