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

Since this group deals with language problems (depending on what you though= t).
Except being a news, this is also a proof that C/C++ can be used as a=20 theoretical language.



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