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)
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
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 …