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 12:45:54

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.

Tobi