A way for P!=NP (2)

From: Denis (dnsflex_nnossppaamm__at_yahoo.com)
Date: 12/19/04 

Date: Sun, 19 Dec 2004 11:52:40 GMT

Some months ago I post a thread a way to investigate for the P!=NP problem.

Now I had analyzed the results of the interesting discussions.

Here I post the base Idea.
---------------------------------------------------------------------------
I define a problem that I call SAT2.
 SAT2(X)=Y

 X is a program passed as parameter

 Y is the result and it is a value such that the program X(Y)=1.

 X is a polynomial program by hypothesis.

 Before proceed I need that SAT2 stay in NP class.

 For definition NP is the class of all programs that halt in polynomial
time in a non deterministic Turing machine.

 I can define the NDTM by a machine composed by a finite series of
quintuples :
 <Qi,Sj,Sk,M,Qh>
 Where Qi is the current state Sj is te current symbol (0,1) Sk is the
writed symbol M is the Head move L=left,R=Right,N=null) Qh is the
destination state.
 For each couple of Qi,Sj I can have more than one Sk,M,Qh.

 These quintuples rapresent a polynomial time complexity program that write
all the possible symbols :
 <Q0,0,0,R,Q0>
 <Q0,1,0,R,Q0>
 <Q0,0,1,R,Q0>
 <Q0,1,1,R,Q0>
 Using this I need N steps in NDTM to write all 2^N possible value of a
 number of N bits.

For Hypothesis X is polynomial in deterministic Turing machine so it is
polynomial also in a NDTM so I can join the two program and execute X for
all possible input Y and obtain a SAT2 program polynomial in a NDTM that
halt after at least the maxim time of computation of X plus the size of Y
and it is again polynomial.

 Now I have SAT2 in NP and I can proceed .

 Assume that exist a program Pb that compute the SAT2 problem in polynomial
time .

 I can write a program Pc(X) that do this :
 if Pb(Pc)=X then
    return 0
 else
    return 1

 So I have the contraddiction and I can solve it if SAT2 is not polynomial
time so SAT2 is NP problem and it is not in P.
---------------------------------------------------------------------------- 

---
The problem of this idea is that it is no possible to detect when a program
is polynomial , it is no possible to identify the complexity of an arbitrary
program X.
A consequence is that SAT2 is not in NP .
Another consequence is that does not exist Pb as polynomial SAT2 becouse
SAT2
does not stay in NP .
Now I try to put an upperbound on the problem.
I reformulate the program
SAT2(X,LY,T)=R,Y
Y is Parameter such that X(Y)=1
Where X is the input program without restriction about its complexity.
LY is the size of the parameter of the program X such that for every Y of
length less or equal to LY  P(Y) where P is a polynomial program of size
less
or equal to the size of X give me the value 0 or 1 using a maximum steps
number T.
So every polynomial program of size less than X give me the result in a time
less than T.
If SAT2 find a parameter Y such that X(Y)=1 in number of steps T and size of
Y
is less of equal to LY it return a value R=1.
When X is a program of different complexity using LY and T it is possible to
stop the computation and SAT2 return a value R=0 .
SAT2 return R=0 when the program X does not stop in T steps and if there are
not parameters Y for X such that X(Y)=1  so if a program X return always 0
SAT2 return R=0 and it means that the value Y is wrong.
Well, now it is clear that SAT2 stay in NP.
For the next step I suppose exist a program Pb that compute SAT2 in DTM in
polynomial time.
Pb(X,LY,T)=R,Y
So I construct a program Pc like this
Pc(GX)
 {
 Split(GX)=>Y,LY,T
 Pb(Pc,LY,T)=>R,Y1
 if R=0 then
    return 1
 else
    {
    if Y1=Y then
       return 0
    else
       return 1
    }
 }
GX  is the parameter .
Split  is a function that split the parameter GX in sub parameters Y LY and
T
 for example I can suppose that GX=Y+LY+T where the operator '+' is
 a bit string concatenator .
Now I can suppose that the length of Pc is less than the length of X so LY
is
correct for Pc as parameter and T is the correct number of steps.
If Pb is polynomial also Pc is polynomial by its construction, Pc halt
always
when Pb halt and in the same time so it has the same complexity of Pb.
The first condition ( if R=0 => return 1 ) set the first contraddiction .
Indeed by the istruction Pb(Pc,LY,T)=>R,Y1 if the program Pc has no a
parameter
Y such that Pc(Y)=1 R=0 but if the length of GX is less than LY  GX is a
valid
parameter such that Pc(GX)=1.
When Lenght of GX is less than LY ? It can not happen if the complexity of
Pb
is exponential becouse in this case T=2^LY so
GX=Y '+' LY '+' 2^LY
LY<=log(2^LY)
LY<log(Y) '+' log(LY) '+' log(2^LY)
LY<log(GX)
Instead in polynomial complexity it is true LY>=log(GX).
The second condition ( if Y1=Y then return 0 else return 1 ) set the second
contraddtion , indeed if the result of Pb(Pc,LY,T)=>R,Y1 is a valid Y1 so
R=1 the second condition return an opposite result.
As I show this program Pc rapresent a contraddiction only if the complexity
of Pb is polynomial .
So the conclusion are SAT2 is polynomial in NDTM and it is not polynomial in
DTM.
Denis.