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

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