wij
2025-02-23 00:01:11 UTC
Reply
Permalinkhttps://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
The text is converted by google translator with minimal modification from
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download
-----------------------------------------------------------------------------
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), O(P) consecutive Ptime
programs 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).
ℕℙ::= {q| q is a judgment problem statement that can be processed by a computer,
q contains the statement of set C, card(C)∈O(2^|q|), verification function
v:C->{true, false}, so that ∀c∈C, v(c) can be calculated in polynomial time,
and, 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 c used to indicate the end
for(c=begin; c!=end; c=next(c)) { // At most O(2^|q|) loops.
// next(c) is a function to obtain 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
}
return false;
}
ANP::= {q| q is the problem that the anp function can calculate}
Proposition 1: ANP=ℕℙ
Proof: anp is the pseudo-C code version described by ℕℙ, and the reason for
its validity is explained in the program comments.
Note: Because 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 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 care
about is whether there are Ptime algorithms for various practical ℕℙℂ
problems. In fact, comparing with the definition in the textbook, the
conditions required by ANP are clearer and stricter, but the
substantive meaning should be the same. This point has some subjective
elements, so I will not elaborate on it.
Proposition 2: ℙ≠ℕℙ
Proof: Since there is an O(2^N) loop in ANP, ANP allows at least some problems
that require O(2^N) steps to compute, that's it.
The common question here is: Is there 'really' an ANP problem that must be
solved in O(2^N)?
Answer: Let X = {a problem in ANP that must be solved with an O(2^N)
algorithm}, then, ℕℙ≤X => X=ℕℙℂ.
Many ℕℙℂ problems are problems that must be solved in O(2^N) --- we
can only answer ℙ≠ℕℙ, we don't know Whether the various ℕℙℂ 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 continue
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<=|q1|-|q2|<=1)
return banp(q1) || banp(q2);// Calculate the sub-questions separately
}
Since the size of the problem is 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 4: The banp(..) in Proposition 3 above can be expanded to express
any general form that can be calculated "faster" by adding object I (defined
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)==true) { // banp_i(q1,I) calculates banp(q1) and provides
// 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 the
Ptime calculation.
Proof: If banp2 can be computed in Ptime, then according to the definition of
polynomial time program, the Ptime program can be merged. solv_remain
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 (without
additional information) can be calculated within Ptime does not hold.
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 thought).
Except being a news, this is also a proof that C/C++ can be used as a
theoretical language.