From Newsgroup: comp.lang.c++

This file is intended a proof of raOrearaoraO. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
The text is converted by google translate with modest modification from https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download
Reader might want to try different translator or different settings. ----------------------------------------------------------------------------- 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 (because 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) consecutive
steps can be considered a single Ptime program.
Reduction::= Computational problem A (the algorithm) can be converted into
computational problem B by Ptime program, denoted as ArenB (because Ptime
conversion itself includes computational problem A, any Ptime problem can
be reduced to each other).
raoraO::= {q| q is a statement decision problem that can be solved by a computer in
O(2^|q|) steps using the following np algorithm template. q contains the
statement of set of Certificate C and the Ptime verification function
v:C->{true, false}. If reac,v(c)=true, then the answer to the problem is true,
and vice versa.}
Because the values of c1size, c2size, ..., cnsize in the following C
language algorithm template are dynamically derived from the description 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 argument
// from problem statement q.
Certificate get_certificate(Problem q, Int idx1, Int idx2,...,Int idxn);
Int c1size = The number obtained from problem q
Int c2size = Same as above
...
Int cnsize = Same as above
bool np(Problem q) {
for(Int idx1 = 0; idx1 < c1size; ++idx1) // n chained for loops
for(Int idx2 = 0; idx2 < c2size; ++idx2)
...
for(Int idxn = 0; idxn < cnsize; ++idxn) {
Certificate c = get_certificate(q, idx1, idx2,..., idxn);
if(v(c)==true) return true;
}
return false;
}
[Note] This definition of raoraO is equivalent to the traditional Turing machine
definition of raoraO. 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 can
surpass the expressive power of a Turing machine. C can be considered
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 this
// 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 element
// does not exist, return the EndC element.
Certificate next_certificate(Problem q, Certificate c);
// v is a Ptime function. v(c)==true 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 = begin_certificate(q); // begin is the first verification data
end = end_certificate(q); // end is the false data EndC used to indicate
// the end
for(c=begin; c!=end;
c=next_certificate(q,c)) {// At most O(2^|q|) loops. next_certificate(c)
// Ptime function for finding the next
// verification data for c
if(v(c)==true) return true; // v:C->{true,false} is a polynomial time
// verification function,
}
return false;
}
Prop 2: raoraO 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(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 q2
// approximately abs(|q1|-|q2|<=O(1))
return banp(q1) || banp(q2); // Compute the sub-problems separately
}
Prop 3: Any two raoraO problems q1 and q2 can be combined into another raoraO problem q,
which can be expressed as q=q1reo q2. The verification data set C and
verification function v for q are defined as follows:
C = 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 q1
// and q2, respectively
}
Prop 4: The banp(..) in Prop 2 above can add an object I (defined as a general
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)==true) { // banp_i(q1,I) computes banp(q1) and
// simultaneously stores any useful information
// 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: raOrearaoraO
Proof: From banp2, we can see that if the solution to a raoraO subproblem always
provides I information that accelerates the computation of other subproblems
,then due to the splitting and combining properties of the raoraO 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. Therefore,
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 Ptime
algorithm. banp2(qreo q') can always obtain I information at Ptime that is not
strongly correlated with q but can accelerate the computation of q by Ptime.
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 raOrearaoraO.
+------------+
| 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) ----------------------------------------------------------------------------- --- Synchronet 3.21a-Linux NewsLink 1.2