Sometimes I come back to think to an old paradox in different form about the SAT problem and the P NP relation.

I expose concisely the main idea.

Suppose I have a solver program for the sat problem SATS ( SAT Solver ) such that

SATS(P) return X if P(X)=1 where P is a boolean formula and X is the value of the variables used in P . If this value X does not exist for P SATS(P) return Ø .

Now given this program SATS is possible to construct the set of all boolean formula instance of SATS for each length of P so I call SATS1 for |P|=1 , … , SATSn for |P|=n .

Now what happen if I construct P in this way (in a C pseudo code)

` P(X)`

{

IF (SATS(P)==X)

return 0

else

return 1

}

this is a contradiction but is not possible to use it … because P must be a boolean formula ( and there is a halting problem argument to avoid this possibility …) .

Ok, but suppose I construct a P with length M such that Pm=Ps1ΛPs2 , I split Pm in 2 parts to obtain a “small” minterm Ps1 of length N and Ps1 constrain Pm to zero if Ps1=0 .

I can write

Pm(X)

{

IF (SATSn(Ps1)==Xs1)

return 0

else

return 1

}

where Xs1 is the subset of values for the variables in Ps1.

Now Pm is convertible in a boolean formula and it is possible to send this to the SATS program .

This is a contradiction but we know is possible to construct SAT solvers so what happen ? Where is the trick?

I think the solution can be related to the size of boolean formula and time complexity and this can help to construct relations …

### Like this:

Like Loading...

*Related*