From Newsgroup: comp.lang.c
On Wed, 2025-11-19 at 15:25 +0800, wij wrote:
The following is a snipet of the revised proof https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
I think the idea of the proof should be valid and easy to understand. The rest
technical apart should be straightforward (could take pages or dozens of pages,
so ignored). But, anyway, something like the C/C++ description is still needed.
Can you find any defects?
OTOH, C/C++ can be the language for for proving math. theorems, lots easier than
TM language to handle and understand. Opinions?
----------------------------------------------------------------------------- Algorithmic Problem::= A computer problem in which the computational steps are a
function of the problem statement's length (size). This problem can be
described asymptotically as the relationship between the problem size and
the computational steps.
Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecutive,
fixed-sized basic operations (because the procedure is a deterministic
process, it is sometimes called a "function" or "operation"). Therefore, as
defined by O(P), O(P) number of Ptime procedures executed consecutively can
also be considered as a single Ptime procedure.
Reduction::= The algorithm for computation problem A can be transformed into
computation problem B by a Ptime procedure, denoted as A≤B (because the
Ptime transformation itself includes the computation of problem A, any two
Ptime problems can be reduced to each other).
ANP::= {q| q is a statement of a decision problem that a computer can solve in
O(2^|q|) steps using the following fnp algorithm template. q contains a
certification dataset C, card(C)∈O(2^|q|), and a Ptime verification function
v:C->{true,false}. If ∃c,v(c)=true, then the answer to problem q is true;
otherwise, it is false.}
// begin_certificate is a Ptime function that retrieves the first
// Certificate element from the problem statement q. If this element does
// not exist, it returns a unique and virtual EndC element.
Certificate begin_certificate(Problem q);
// end_certificate is a Ptime function that retrieves the element EndC from
// the problem statement q.
Certificate end_certificate(Problem q);
// next_certificate is a Ptime function that retrieves the next element of
// c from the certification dataset C. 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 if c is the element expected by the
// problem.
bool v(Certificate c);
bool fnp(Problem q) {
Certificate c, begin, end; // Declare the certification data variable
begin= begin_certificate(q); // begin is the first certification 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|) steps.
// next_certificate(c) is a Ptime
// function to get the next
// certification data of c
if(v(c) == true) return true; // v: C->{true, false} is a polynomial
// time verification function.
}
return false;
}
Since a continuous O(P) number of Ptime functions (or instructions) can be
combined into a single Ptime function, at roughly this complexity analysis,
any Ptime function can be added, deleted, merged/split in the algorithm
steps without affecting the algorithm's complexity. Perhaps in the end, only
the number of decision branches needs to be considered.
An ANP problem q can be expressed as q<v, C>, where v = Ptime verification
function, and C = certification dataset (description).
[Note] According to Church-Turing conjecture, no formal language can
surpass the expressive power of a Turing machine (or algorithm, i.e.,
the decisive operational process from parts to the whole). C
language can be regarded as a high-level language of Turing machines,
and as a formal language for knowledge or proof.
Prop1: ANP = ℕℙ
Proof: Omitted (The proof of the equivalence of ANP and the traditional
Turing machine definition of ℕℙ is straightforward and lengthy, and
not very important to most people. Since there are already thousands
of real-world ℕℙℂ problems available for verification, the definition
of ANP does not rely on NDTM theory)
Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subproblems
q1<v,C1>, q2<v,C2), where C = C1∪C2.
Proof: The certification dataset can be recursively partitioned 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); // Split the certification dataset C
// to form q1,q2, in which the number of
// certificates are roughly the same.
return banp(q1) || banp(q2); // Compute the subproblems respectively
}
Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
problem q, denoted as q = q1 ⊕ q2. The certification dataset C and the
verification function v of q are defined as follows:
C = C1 ∪ C2 // C1 and C2 are the certification datasets of q1 and q2
// respectively
bool v(x) {
return v1(x) || v2(x); // v1 and v2 are the verification functions of
// q1 and q2 respectively
}
Therefore, we have the identity: q1<v1,C1>⊕ q2<v2,C2> = q<v1||v2, C1∪C2>.
Prop4: ℙ=ℕℙ iff the algorithm fnp in the ℕℙ definition (or ℕℙℂ algorithm) can be
replaced by a Ptime algorithm.
Proof: Omitted
Prop5: For subproblems q1<v,C1> and q2<v,C2> (same v), if C1 ∩ C2 = ∅, then
there is no information in problem q1 that is sufficient in terms of
order of complexity to speed up the computation of q2.
Proof: An AuxInfo object, called 'auxiliary information', can be added to
banp to store the results after computation of a certain problem q,
as rewritten as banp2. Depending on the content of the auxiliary
information, banp2 can represent possible algorithms for ANP/ℕℙℂ
problems with complexity ranging from O(N) to O(2^N).
bool banp2(Problem q, AuxInfo* ibuf) { // Calculate q and write the
// obtained auxiliary information to *ibuf
// Check and initialize *ibuf
if(certificate_size(q)<Thresh) {
return solve_thresh_case(q,ibuf);
}
Problem q1,q2;
split_certificate(q,q1,q2);
AuxInfo I; // I stores information to help solve problems.
if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes subproblem
// q1 and stores any auxiliary information that
// can be derived from q1 in I.
write_ibuf1(ibuf,q); // Write auxiliary information
return true; // The information obtained from subproblem q1
// is valid for any problem q.
}
bool rv=banp2_i(q2,I); // Solve q2 with given information I, effective
// regardless of the source of the problem.
write_ibuf2(ibuf,q);
return rv;
}
The above `banp2_i` does not care which ANP problem (including trivial
problems) the given information `I` originates from. The `I` generated can
also provide auxiliary information for almost all other ANP problems.
Since the auxiliary information I obtained from the trivial subproblems
cannot provide sufficient information to accelerate computation to the
extent of improving the complexity order for every subproblem, the
proposition is proved.
Conclusion: Since banp2 algorithm cannot be faster than O(2^N), there is no
algorithm faster than O(2^N) for ℕℙℂ problems. Therefore, ℙ≠ℕℙ.
[Note] In fact, from Prop4, the fnp definition of the ℕℙ problem, and the
definition of the Ptime procedure, it can also be roughly seen that
ℙ≠ℕℙ.
-----------------------
I feel the 'assertion' in Prop5 "the trivial subproblems cannot provide
sufficient information to accelerate computation to the
extent of improving the complexity order for every subproblem, the
proposition is proved." is abrupt. Better way of phrasing?
--- Synchronet 3.21a-Linux NewsLink 1.2