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 translate with modest modification from https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/dow= nload
Reader might want to try different translator or different settings.

---------------------------------------------------------------------------=
--
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 (bec= ause a
program is a deterministic process, it is sometimes called a "function"=
,
"operation," or "operation") that has O(P) consecutive, fixed steps.
Therefore, by the O(P) definition, a Ptime program with O(P) consecutiv=
e
steps can be considered 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 statement decision problem that can be s= olved by a computer in
O(2^|q|) steps using the following np algorithm template. q contains th=
e
statement of set of Certificate C and the Ptime verification function
v:C->{true, false}. If =E2=88=83c,v(c)=3Dtrue, then the answer to the p= roblem is true,
and vice versa.}

Because the values of c1size, c2size, ..., cnsize in the following C
language algorithm template are dynamically derived from the descriptio=
n of
problem q. Strictly, they are equivalent templates, the actual pattern = may
differ somehow.

// get_certificate is a Ptime function.
// Extracts the Certificate element corresponding to the function argum= ent
// from problem statement q.
Certificate get_certificate(Problem q, Int idx1, Int idx2,...,Int idxn)=
;

Int c1size =3D The number obtained from problem q
Int c2size =3D Same as above
...
Int cnsize =3D Same as above

bool np(Problem q) {
for(Int idx1 =3D 0; idx1 < c1size; ++idx1) // n chained for loops
for(Int idx2 =3D 0; idx2 < c2size; ++idx2)
...
for(Int idxn =3D 0; idxn < cnsize; ++idxn) {
Certificate c =3D get_certificate(q, idx1, idx2,..., idxn);
if(v(c)=3D=3Dtrue) return true;
}
return false;
}

[Note] This definition of =E2=84=95=E2=84=99 is equivalent to the tradi= tional Turing machine
definition of =E2=84=95=E2=84=99. The details of this proof are =
a bit lengthy and not
very meaningful to most people, so I'll omit them.

[Note] According to the Church-Turing Conjecture, no formal language ca=
n
surpass the expressive power of a Turing machine. C can be consi= dered
a high-level language or "specification" of a Turing machine.

Prop 1: Since a consecutive O(P) number of Ptime functions (or instructions=
) can
be combined into a single Ptime function, the above np algorithm is
equivalent to the following np1 algorithm with a single for loop:

// begin_certificate is a Ptime function.
// Extract the first Certificate element from problem statement q. If t= his
// element does not exist, return the unique and virtual EndC element.
Certificate begin_certificate(Problem q);

// end_certificate is a Ptime function.
// Extract the element EndC from problem statement q.
Certificate end_certificate(Problem q);

// next_certificate is a Ptime function.
// Extract the element after c from problem statement q. If this elemen=
t
// does not exist, return the EndC element.
Certificate next_certificate(Problem q, Certificate c);

// v is a Ptime function. v(c)=3D=3Dtrue iff c is the element expected =
by the
// problem.
bool v(Certificate c);

bool np1(Problem q) {
Certificate c, begin, end; // Declare the verification data variable
begin =3D begin_certificate(q); // begin is the first verification da=
ta
end =3D end_certificate(q); // end is the false data EndC used to ind= icate
// the end
for(c=3Dbegin; c!=3Dend;
c=3Dnext_certificate(q,c)) {// At most O(2^|q|) loops. next_certifi= cate(c)
// Ptime function for finding the next
// verification data for c
if(v(c)=3D=3Dtrue) return true; // v:C->{true,false} is a polynomia=
l time
// verification function,
}
return false;
}

Prop 2: =E2=84=95=E2=84=99 problems can always be split into two sub-proble= ms.
Proof: The verification data set can be split into two and processed
recursively as follows:

bool banp(Problem q) {
if(certificate_size(q)<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 sub-problems of size q1 and q=
2
// approximately abs(|q1|-|q2|<=3DO(1))
return banp(q1) || banp(q2); // Compute the sub-problems separately
}

Prop 3: Any two =E2=84=95=E2=84=99 problems q1 and q2 can be combined into = another =E2=84=95=E2=84=99 problem q,
which can be expressed as q=3Dq1=E2=8A=95 q2. The verification data set=
C and
verification function v for q are defined as follows:

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

bool v(x) {
return v1(x) || v2(x); // v1, v2 are the verification functions for q=
1
// and q2, respectively
}

Prop 4: The banp(..) in Prop 2 above can add an object I (defined as a gene= ral
form that stores information about how to accelerate the computation of=
a
problem to Ptime after completing the computation of a problem):

bool banp2(Problem q) {
if(certificate_size(q)<Thresh) {
return solve_thresh_case(q);
}
Problem q1,q2;
split_certificate(q,q1,q2);
Info I; // I stores information about accelerating the computation of=
the
// problem
if(banp_i(q1,&I)=3D=3Dtrue) { // banp_i(q1,I) computes banp(q1) and
// simultaneously stores any useful informa= tion
// that can be derived from q1 into I.
return true;
}
return solv_remain(q2,I); // Solve the remaining problem q2 given the
// information in I.
}

Prop 5: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99
Proof: From banp2, we can see that if the solution to a =E2=84=95=E2=84= =99 subproblem always
provides I information that accelerates the computation of other subpro= blems
,then due to the splitting and combining properties of the =E2=84=95=E2= =84=99 problem, The I
from a fixed-type problem of trivial problems is also valid for
solve_remain(q2,I). In other words, I is effetively ineffective. Theref= ore,
no information I exists that can accelerate banp2 to Ptime.

For example, from q, we can construct q' of the same size and with a Pt= ime
algorithm. banp2(q=E2=8A=95 q') can always obtain I information at Ptim=
e that is not
strongly correlated with q but can accelerate the computation of q by P= time.
This is impossible.

The complexity of the banp (equivalent to np) algorithm is O(2^N).
No algorithm exists that can accelerate the computation to Ptime, so = =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]
[4] https://sourceforge.net/projects/cscall/files/MisFiles/Computation-en.= txt/download
(Computing concepts and term definition) ---------------------------------------------------------------------------=
--


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