Thinking about P & NP

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)

return 0
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

IF (SATSn(Ps1)==Xs1)
return 0
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 …


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s