Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Updated P!=NP proof
Date: Mon, 31 Mar 2025 14:33:18 +0800
Organization: A noiseless patient Spider
Lines: 257
Message-ID: <5f35dd92bc4e69a18c231cbd388554e62155efe1.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 31 Mar 2025 08:33:19 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1597624ed8e36a6868c5a4eebe6cdeec";
	logging-data="3749208"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Ss3SKxgbK2cTTuSJjtdu9"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:fHT6vZzSC/kYPi97P+8YI+L/plg=

The P!=3DNP proof is updated, and a second proof, both are easier to verify=
..

Key word "verify" and better be easy to. This is the basics of science.

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
This file is intended a proof of =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. The =
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 modest modification from
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/dow=
nload
=20
The following contains two proofs, one using algorithm and the other one us=
ing
Turing Machine.
=20
---------------------------------------------------------------------------=
--
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), a Ptime program wit=
h
    O(P) consecutive executions can also be regarded as a single Ptime prog=
ram.

Reduction::=3D Computational problem A (the algorithm) can be converted int=
o=20
    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).

ANP::=3D {q| q is a decision problem statement that can be processed by a
    computer. q contains a set statement C, card(C) is no greater than O(2^=
|q|),
    Ptime verification function v:C->{true, false}. If =E2=88=83c,v(c)=3Dtr=
ue, then the
    answer to the question=3Dtrue, and vice versa}=20

    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 data to indicate the=
 end
      for(c=3Dbegin; c!=3Dend; c=3Dnext(c)) { // At most O(2^|q|) loops.
                                        // next(c) is a Ptime function for =
the
                                        //  next verification data of c
        if(v(c)=3D=3Dtrue) return true; // v:Certificate->{true,false} is a
                                    //  polynomial time function, and=20
                                    //  anp(q)=3D=3Dtrue if =E2=88=83c, v(c=
)=3D=3Dtrue.
                                    //  v(c)=3D=3Dfalse denotes verificatio=
n failure
                                    //  (any reason).
      }
      return false;
    }=20

Proposition 1: ANP=3D=E2=84=95=E2=84=99
  Proof: anp is a C pseudo-code version of =E2=84=95=E2=84=99 (which can si=
mulate NDTM), and
         the reason for its validity has been roughly explained in the prog=
ram
         comments.

  Note: Since there are many ways to define =E2=84=95=E2=84=99, the definit=
ion of ANP (Another
        NP) is to make it easier to deal with confusion. The general defini=
tion
        of =E2=84=95=E2=84=99 does not explicitly require O(2^N) loops and =
C sets. The
        verification function v may only require existence, not "given", an=
d its
        false state has no time limit, nor does it say that all elements of=
 C=20
        must be tested one by one. But these are not important and can be
        handled. However, the judgment of ANP=3D=E2=84=95=E2=84=99 is very =
direct but a bit
        subjective, so I will not elaborate on it.

Proposition 2: 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()<Thresh) { // Thresh is a small constant
            return solve_thresh_case(q);      // Solve q in constant time
          }
          Problem q1,q2;
          split_certificate(q,q1,q2); // Divide the verification data set C=
 in
                                      // q into two groups of size.  q1 and=
 q2
                                      // are approx. the same (0<=3D|q1|-|q=
2|<=3D1)
          return banp(q1) || banp(q2);// Calculate the subproblem separatel=
y
        }

     Since the size of subproblems can be only 1 less, the computational co=
mplexity
     of banp(q) is W(|q|)<=3D W(|q|-1)+W(|q|-1)=3D 2^(|q|-1)*W(1), W(1)=3D1=
.. That is,
     Complexity(ANP)<=3DO(2^N).

Proposition 3: Any two ANP problems q1 and q2 can be synthesized into anoth=
er
     ANP problem q, which can be written as q=3Dq1=E2=8A=95 q2. The verific=
ation data set
     C and verification function v of q are defined as follows:

     C=3D C1||C2                // C1, C2 are the verification data sets of=
 q1 and
                              // q2 respectively

     v(x) {
       return v1(x) || v2(x); // v1,v2 are the verification functions of q1=
,q2
                              // respectively
     }

Proposition 4: The banp(..) in Proposition 2 above can be expanded to a gen=
eral
  form that can solve ANP problem "faster" by adding object I (defined to
  contain all possible speed up information that can be obtained after the
  calculation):

  bool banp2(Problem q) {
    if(q.certificate().size()<Thresh) {
      return solve_thresh_case(q);
    }
    Problem q1,q2;
    split_certificate(q,q1,q2);
    Info I;                   // I stores problem acceleration information
    if(banp_i(q1,&I)=3D=3Dtrue) { // banp_i(q1,I) calculates banp(q1) and p=
rovides
                              // any useful information that can be derived
                              // from q1, and store into I
      return true;
    }
    return solv_remain(q2,I); // Given I information, solve the remaining q=
2
  }

Proposition 5: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99
  Proof: From banp2, if the solution of a certain ANP
         subproblem can always provide the I information to accelerate the
         calculation of other subproblems, then any source of I is valid fo=
r
         solv_remain(q2,I), so I has no actual effect (I can be derived fro=
m
         trivial problems), so it can be rewritten as solv_remain(q2).
         Similarly, since solv_remain does not require external I, banp_i(q=
1,&I)
         can be rewritten as banp_i(q1)... Result: banp2 is isomorphic to b=
anp.
         In other words, there is no "the I information that can speed up t=
he
         calculation" as defined by banp2, that is, there is no faster algo=
rithm
         than anp for ANP problems.

         This proof actually shows that the verification data of the ANP pr=
oblem
         can be independent of each other. Therefore, in terms of algorithm=
, if
========== REMAINDER OF ARTICLE TRUNCATED ==========