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
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}

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
// anp(q)=3D=3Dtrue if =E2=88=83c, v(c= )=3D=3Dtrue.
// v(c)=3D=3Dfalse denotes verificatio=
n failure
// (any reason).
}
return false;
}

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
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
the problem contains O(X) verification data, O(X) verification 'st= eps'
are needed in the worst case.

+--------------------+
| Auxilliary Proof 1 |
+--------------------+
STM::=3D A Turing machine represented by a string {0,1}* (blank tape). This
Turing machine computes the function {0,1}*->{0,1}. (In the followin=
g
description, we can imagine that the STM is an executable file writt=
en in
machine language, and the STM is separate from its input).

int_cast(x)::=3D An operator that casts the STM x to a natural number.

Let s,f=E2=88=88STM. s(f)=3D1 iff =E2=88=83c,c<=3Dint_cast(f), f(c)=3D1. Th=
e function of s can be
described by the following C pseudo-code:

int s(STM f) {
for(int c=3D0; c<=3Dint_cast(f); ++c) {
if(simu(f,c)) return 1; // Parallel simulation f(c). If simu determ= ines
// that f cannot be executed normally (e.g.=
non-
// qualified STM), simu(f,c) returns 0
}
return 0;
}

Therefore:
1. If f is confined as a Ptime STM, then Problem(s)=3D=E2=84=95=E2=84= =99 (i.e. the problem
solved by s is a =E2=84=95=E2=84=99 problem. Proof of this asserti=
on is quite direct
and trivial, so it is omitted).
2. If Problem(s)=E2=8A=86=E2=84=99 holds, then s can be the argument =
of s. According to
the definition of s, s(s) can have the following conditions:

s(0) s(1) ... s(s) =3D result // s(c) on the left is abbr. of simu(s,c=
)
------------------------
T T ... U =3D T // T: Ptime timeout
T 0 ... U =3D T
T 1 ... U =3D 1 // 1: s(s)=3D1
0 T ... U =3D T
0 0 ... U =3D U // U: Self-reference, undecidable
0 1 ... U =3D 1
1 T ... U =3D 1
1 0 ... U =3D 1
1 1 ... U =3D 1

Note: The judgment method of 'Ptime timeout' is: Preset the upper limit=
of
of the Ptime step of s(s) as t. If the execution steps of s(s) ex= ceed
t, it is judged as 'Ptime timeout'.

Because s(s) may encounter Ptime timeout or situation that cannot be
determined. Therefore, s cannot be a Ptime STM, therefore, =E2=84=99=E2= =89=A0=E2=84=95=E2=84=99

+------------+
| 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] ---------------------------------------------------------------------------=
--



--- MBSE BBS v1.1.1 (Linux-x86_64)
* Origin: A noiseless patient Spider (3:633/280.2@fidonet)