Re: A way for P!=NP

From: Denis Flex (Denis_at_Denis.com)
Date: 09/23/04 

Date: Thu, 23 Sep 2004 11:17:59 GMT

"Denis" <Denis@Denis.com> ha scritto nel messaggio
news:jJX2d.9797$zF3.258919@twister2.libero.it...
> Assume that exist a program Pb that compute the SAT problem in polynomial
> time .
> For convenience I fix false=0 true=1
> Now it is possible to write a program Pc like this:
>
> X is the parameter
>
> if Pb(Pc)=X then
> return 0
> else
> return 1
>
>
> This is a contraddiction!
> This is an impossible program!
> If Pb is polynomial Pc is polynomial and so I can use Pc as parameter of
> Pb.
> The only way to resolve this contraddiction is that Pb is not polynomial
> time so NP!=P.
>
> Denis.
>

I send the same post also in comp.theory and after some argument I find
there is a problem :

1) There is a plynomial reduction to all P programs in a boolean formula
only for a limited bound .
2) There is no a way to separate P programs from exponential program so Pc
is not in P.

Denis.