The P!=NP 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.
=================This file is intended a proof of ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/downloadThe text is converted by google translator with modest modification from
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download The following contains two proofs, one using algorithm and the other one using
Turing Machine.
-----------------------------------------------------------------------------
Algorithmic Problem::= A computer problem in which the number of computational
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)::= 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 with
O(P) consecutive executions can also be regarded as a single Ptime program.
Reduction::= Computational problem A (the algorithm) can be converted into
computational problem B by Ptime program, denoted as A≤B (because Ptime
conversion itself includes computational problem A, any Ptime problem can
be reduced to each other).
ANP::= {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 ∃c,v(c)=true, then the
answer to the question=true, 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 = get_begin_certificate(C); // begin is the first verification data
end = get_end_certificate(C); // end is a fake data to indicate the end
for(c=begin; c!=end; c=next(c)) { // At most O(2^|q|) loops.
// next(c) is a Ptime function for the
// next verification data of c
if(v(c)==true) return true; // v:Certificate->{true,false} is a
// polynomial time function, and
// anp(q)==true if ∃c, v(c)==true.
// v(c)==false denotes verification failure
// (any reason).
}
return false;
}
Proposition 1: ANP=ℕℙ
Proof: anp is a C pseudo-code version of ℕℙ (which can simulate NDTM), and
the reason for its validity has been roughly explained in the program
comments.
Note: Since 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 explicitly 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 and can be
handled. However, the judgment of ANP=ℕℙ 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<=|q1|-|q2|<=1)
return banp(q1) || banp(q2);// Calculate the subproblem separately
}
Since the size of subproblems can be only 1 less, the computational complexity
of banp(q) is W(|q|)<= W(|q|-1)+W(|q|-1)= 2^(|q|-1)*W(1), W(1)=1.. That is,
Complexity(ANP)<=O(2^N).
Proposition 3: Any two ANP problems q1 and q2 can be synthesized into another
ANP problem q, which can be written as q=q1⊕ q2. The verification data set
C and verification function v of q are defined as follows:
C= 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 general
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)==true) { // banp_i(q1,I) calculates banp(q1) and provides
// 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 q2
}
Proposition 5: ℙ≠ℕℙ
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 for
solv_remain(q2,I), so I has no actual effect (I can be derived from
trivial problems), so it can be rewritten as solv_remain(q2).
Similarly, since solv_remain does not require external I, banp_i(q1,&I)
can be rewritten as banp_i(q1)... Result: banp2 is isomorphic to banp.
In other words, there is no "the I information that can speed up the
calculation" as defined by banp2, that is, there is no faster algorithm
than anp for ANP problems.
This proof actually shows that the verification data of the ANP problem
can be independent of each other. Therefore, in terms of algorithm, if
the problem contains O(X) verification data, O(X) verification 'steps'
are needed in the worst case.
+--------------------+
| Auxilliary Proof 1 |
+--------------------+
STM::= A Turing machine represented by a string {0,1}* (blank tape). This
Turing machine computes the function {0,1}*->{0,1}. (In the following
description, we can imagine that the STM is an executable file written in
machine language, and the STM is separate from its input).
int_cast(x)::= An operator that casts the STM x to a natural number.
Let s,f∈STM. s(f)=1 iff ∃c,c<=int_cast(f), f(c)=1. The function of s can be
described by the following C pseudo-code:
int s(STM f) {
for(int c=0; c<=int_cast(f); ++c) {
if(simu(f,c)) return 1; // Parallel simulation f(c). If simu determines
// 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)=ℕℙ (i.e. the problem
solved by s is a ℕℙ problem. Proof of this assertion is quite direct
and trivial, so it is omitted).
2. If Problem(s)⊆ℙ 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) = result // s(c) on the left is abbr. of simu(s,c)
------------------------
T T ... U = T // T: Ptime timeout
T 0 ... U = T
T 1 ... U = 1 // 1: s(s)=1
0 T ... U = T
0 0 ... U = U // U: Self-reference, undecidable
0 1 ... U = 1
1 T ... U = 1
1 0 ... U = 1
1 1 ... U = 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) exceed
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, ℙ≠ℕℙ
+------------+
| 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]
-----------------------------------------------------------------------------
Updated P!=NP proof