Re: A P!=NP proof for review.

wij <wyniijj5@gmail.com> wrote:

This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
 
The text is converted by google translator with minimal modification from
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download
 

<snip>

  Note: Because there are many ways to define ℕℙ, the definition of ANP
       (Another NP) is to make it easier to deal with confusion. The general
       definition of ℕℙ does not require O(2^N) loops and C sets. The
       verification function v may only require existence, not "given", and
       its false state has no time limit, nor does it say that all elements of
       C must be tested one by one. But these are not important.

Sorry, this is crucial element.

       What we care
       about is whether there are Ptime algorithms for various practical ℕℙℂ
       problems. In fact, comparing with the definition in the textbook, the
       conditions required by ANP are clearer and stricter, but the
       substantive meaning should be the same. This point has some subjective
       elements, so I will not elaborate on it.

The devil is in details.  It was observed (short after P versus NP
problem was clearly formulated) that by generalizing problem and
changing definitions one can make it go one way or the other.
Precise formulation uses notion of computatiom with oracles: you
are given an extra function F which solves some possibly hard problem,
but you are "charged" only unit cost for using such a function.
With one F we have P(F) = NP(F), with other F we (provably!) have
P(F) != NP(F).  Most methods of proving work the same regardless
of F, so can not solve P versus NP.

To illustrate some of troubles consider a silly C function below:

bool right_guess(long i) {
    return (i == MAGIC_CONSTANT);
}

where MAGIC_CONSTANT is a fixed constant of type long.  Your
task is to find i such that right_guess(i) returns true.  If
you are allowed to look at MAGIC_CONSTANT, than the task is
trivial, you just read the answer.  If you are only allowed to
call right_guess, but are not allowed to look at MAGIC_CONSTANT,
then problem is provably hard: you can not do better than looking
at large fraction of possibilities.  P versus NP problem is
analogous to "obfuscated C" problem: you are given source code
of right_guess, but this source is written in obfuscated form,
so that MAGIC_CONSTANT is not visible (actually, right_guess may
be computing something quite different).  So in C terms, the
P versus NP question is: can you de-obfuscate given function
well enough to decide if it returns true for some value.
Of course "can" means doing it in polynomial time and we
assume that function can do its computation in polynomial
time.

Note: C is not good fit for theoretical problems because basic
C type have fixed and rather small size.  For example current
popular implementations have 32-bit int type.  Replacing
long by int in right_guess we get problem which can be easily
solved by brute force on normal PC.  Using implementation with
64-bit long we get problem which on current machines is
realistically hard, but possibly solvable on bigger machines.
Theoretical texts avoid such problems by using theoretical infinte
machines (like Turing machine).  I hinted above at another
possibility: with finite machines real question is we can
find answer substantially faster than using brute force.
But "substantially faster" would need more precise formulation
and speed of real machines go beyond what C specifies.

--
                              Waldek Hebisch