Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.lang.c
Subject: A P!=NP proof for review.
Date: Sun, 23 Feb 2025 08:01:11 +0800
Organization: A noiseless patient Spider
Lines: 189
Message-ID: <ce3f0c1fdbf0cc7212ca97edbd5f525c254a7c02.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 01:01:12 +0100 (CET)
Injection-Info: dont-email.me; posting-host="df76b8c94380963b9ae96cafc3d5649d";
	logging-data="199336"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19XvpolrZpn24gNqB0NzomP"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:fIBZ0XBoUQuwNiWkIVe8f+Jvfas=
Bytes: 8551

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()<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 sub-questions separa=
tely
        }

  Since the size of the problem is only 1 less, the computational complexit=
y 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 4: The banp(..) in Proposition 3 above can be expanded to expre=
ss
  any general form that can be calculated "faster" by adding object I (defi=
ned
  as storing all the information that can be obtained after the problem is
  calculated):
  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 solving 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, stored in I
      return true;
    }
    return solv_remain(q2,I); // Given I information, solve the remaining
                              // banp(q2)
  }

Proposition 5: Without more additional information, banp cannot complete th=
e
  Ptime calculation.
  Proof: If banp2 can be computed in Ptime, then according to the definitio=
n of
        polynomial time program, the Ptime program can be merged. solv_rema=
in
        can calculate I by itself, and I in banp2 is unnecessary. Therefore=
,
        banp2 degenerates into the banp (Proposition 3) algorithm. But the
        complexity of banp is O(2^N) as a premise fact. Therefore, this is =
a
        contradictory assumption. Therefore, the assumption that banp (with=
out
        additional information) can be calculated within Ptime does not hol=
d.

References:
 [1] THEORY OF COMPUTATION [Deric Wood]
 [2] ALGORITHMICS, Theory and Practice [Gilles Brassard, Paul Bratley]
 [3] AN INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA [Peter Linz]
---------------------------------------------------------------------------=
--

========== REMAINDER OF ARTICLE TRUNCATED ==========