Warning: mysqli::__construct(): (HY000/1040): Too many connections in D:\Inetpub\vhosts\howardknight.net\al.howardknight.net\includes\artfuncs.php on line 21
Failed to connect to MySQL: (1040) Too many connectionsPath: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: wij Newsgroups: comp.theory Subject: A P!=NP proof for review. Date: Sun, 23 Feb 2025 07:46:40 +0800 Organization: A noiseless patient Spider Lines: 183 Message-ID: <0f193ae7e4bb45a125490a4fccb077f742680432.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Sun, 23 Feb 2025 00:46:43 +0100 (CET) Injection-Info: dont-email.me; posting-host="df76b8c94380963b9ae96cafc3d5649d"; logging-data="199336"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX184LKHvgHs9dFcGre0Nn6Dn" User-Agent: Evolution 3.54.3 (3.54.3-1.fc41) Cancel-Lock: sha1:+kO4OGHv2GUbG2PXrVXdTfsHh40= Bytes: 8370 This file is intended a proof that =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. Th= e contents may be updated anytime. https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow= nload The text is converted by google translator with minimal modification from https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/dow= nload ---------------------------------------------------------------------------= -- Algorithmic Problem::=3D A computer problem in which the number of computat= ional steps is a function of the problem size. This problem can be described asymptotically between the size of the problem and the number of computational steps. Polynomial time program (or Ptime program)::=3D an algorithmic program with= O(P) consecutive, fixed number of execution steps (because the program is a deterministic process, it is sometimes called a "function", "function" = or "operation"). Therefore, by the definition of O(P), O(P) consecutive Pt= ime programs can also be regarded as a single Ptime program. Reduction::=3D Computational problem A (the algorithm) can be converted int= o computational problem B by Ptime program, denoted as A=E2=89=A4B (becau= se Ptime conversion itself includes computational problem A, any Ptime problem c= an be reduced to each other). =E2=84=95=E2=84=99::=3D {q| q is a judgment problem statement that can be p= rocessed by a computer, q contains the statement of set C, card(C)=E2=88=88O(2^|q|), verificati= on function v:C->{true, false}, so that =E2=88=80c=E2=88=88C, v(c) can be calculate= d in polynomial time, and, if =E2=88=83c,v(c)=3Dtrue, then the answer to the question=3Dtrue,= and vice versa} From the above definition, we can get the C pseudo-code description anp= : bool anp(Problem q) { Certificate c,begin,end; // declare verification data variable begin =3D get_begin_certificate(C); // begin is the first verificatio= n data end =3D get_end_certificate(C); // end is a fake c used to indicate t= he end for(c=3Dbegin; c!=3Dend; c=3Dnext(c)) { // At most O(2^|q|) loops. // next(c) is a function to obtain = the // next verification data of c if(v(c)=3D=3Dtrue) return true; // v:Certificate->{true,false} is a // polynomial time function, and // anp(q)=3D=3Dtrue if =E2=88=83c, v(c= )=3D=3Dtrue } return false; } ANP::=3D {q| q is the problem that the anp function can calculate} Proposition 1: ANP=3D=E2=84=95=E2=84=99 Proof: anp is the pseudo-C code version described by =E2=84=95=E2=84=99, = and the reason for its validity is explained in the program comments. Note: Because there are many ways to define =E2=84=95=E2=84=99, the defin= ition of ANP (Another NP) is to make it easier to deal with confusion. The genera= l definition of =E2=84=95=E2=84=99 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. What we ca= re about is whether there are Ptime algorithms for various practical = =E2=84=95=E2=84=99=E2=84=82 problems. In fact, comparing with the definition in the textbook, th= e conditions required by ANP are clearer and stricter, but the substantive meaning should be the same. This point has some subjecti= ve elements, so I will not elaborate on it. Proposition 2: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 Proof: Since there is an O(2^N) loop in ANP, ANP allows at least some pro= blems that require O(2^N) steps to compute, that's it. The common question here is: Is there 'really' an ANP problem that must b= e solved in O(2^N)? Answer: Let X =3D {a problem in ANP that must be solved with an O(2^N) algorithm}, then, =E2=84=95=E2=84=99=E2=89=A4X =3D> X=3D=E2=84=95= =E2=84=99=E2=84=82. Many =E2=84=95=E2=84=99=E2=84=82 problems are problems that must = be solved in O(2^N) --- we can only answer =E2=84=99=E2=89=A0=E2=84=95=E2=84=99, we don't kn= ow Whether the various =E2=84=95=E2=84=99=E2=84=82 problems themselves 'really' must be calculated in O(2^N) steps. The proof of Proposition 2 may be too simple to believe, so we will continu= e some verification in another direction. Proposition 3: ANP problems can always be split into two sub-problems. Proof: The verification data set can be split into two and processed recursively as follows: bool banp(Problem q) { if(q.certificate().size()