The following is a snipet of the revised proof https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow nload

I think the idea of the proof should be valid and easy to understand. The r
est
technical apart should be straightforward (could take pages or dozens of pa ges,
so ignored). But, anyway, something like the C/C++ description is still nee ded.
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?

--------
??::= {q| q is a decision problem that a computer solves
in O(2^|q|) steps using
the following fnp algorithm template. q contains a verification data
set
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; oth
erwise, it is
false.}

// begin_certificate is a Ptime function that retrieves the first
// Certificate element from the problem statement q. If this element do
es
// 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 problem statement q. If this element does not exist, retu
rn
// the EndC element.
Certificate next_certificate(Problem q, Certificate c);

// v is a Ptime function. v(c)==true if c is the element expected b
y the
// problem.
bool v(Certificate c);

bool fnp(Problem q) {
Certificate c, begin, end; // Declare the verification data variabl
e
begin= begin_certificate(q); // begin is the first verification dat
a
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 the Ptime
// function to get the next
// verification data of c
if(v(c) == true) return true; // v: C->{true, false} is the p olynomial
// time verification function.
}
return false;
}

Since a continuous O(P) number of Ptime functions (or instructions) can
be
combined into a single Ptime function, if the complexity of each functi
on is
Ptime, and the smallest unit of complexity is also Ptime, then it's rou ghly
the same. Any Ptime function can be added, deleted, merged, or split in
the
algorithm without affecting the algorithm's complexity. Perhaps in the end,
only the number of decision branches needs to be considered.

[Note] This definition of ?? is equivalent to the tradi
tional Turing machine
definition of ??. The proof of equivalence is pl
ain and lengthy, and
not very important to most people, so it is omitted.

[Note] According to the Church-Turing conjecture, no formal language ca
n
surpass the expressive power of a Turing machine (or algorithm) (i.e.
the decisive operational process from part to whole). C language
can
be regarded as a high-level language for Turing machines, and as
a
formal language for knowledge or proof.

Problem Q::= Given plaintext a, ciphertext b, decoder d, and key length k
len.
The key is a Ptime program. Problem Q determines whether there exists a
key c such that d(b,c)=a.

Problem Q can be computed using the following C/C++ pseudo code as fnp
by
definition; therefore, Q???.
Plaintext a, ciphertext b, decoder d, and the length of key klen are al
l
obtained from q:

bool f(Problem q) {
int MaxKey= ... // klen=maximum value of key (O( 2^klen))
for(int c=1; c<=MaxKey; ++i) {
if(equ(d(b,c),a)) return true; // Polynomial-time verification
// (If c is not a valid program, the
n d
// returns a value such that equ tes
t
// result is false)
}
return false;
}

Since the key is a freely written program, Each decription algorithm (k
ey)
is essentially independent, and the given problem q may contain no
information about the algorithm's logic (knowledge of one key cannot be
used to deduce information about another).
Therefore, at least O(2^|klen|) possible key values must be tested one
by
one. Thus, the complexity of problem q is O(2^N).
---------------

(Thanks to olcott, this proof was origianlly inspired by POO Halt, where th
e
P-NP proof based on Halting Problem was found invalid)


--- PyGate Linux v1.5
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 2025-11-19 at 15:23 +0800, wij wrote:

The following is a snipet of the revised proof https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/d

ownload

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 n

eeded.

Can you find any defects?

OTOH, C/C++ can be the language for for proving math. theorems, lots easi

er than

TM language to handle and understand. Opinions?

---------------------------------------------------------------------------
--
Algorithmic Problem::= A computer problem in which the computational step
s are a
function of the problem statement's length (size). This problem can be
described asymptotically as the relationship between the problem size a
nd
the computational steps.

Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecut
ive,
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 i
nto
computation problem B by a Ptime procedure, denoted as AóB (bec
ause 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 sol
ve 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 verifica
tion function
v:C->{true,false}. If ?c,v(c)=true, then the answer to proble
m 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 do
es
// 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 b
y the
// problem.
bool v(Certificate c);

bool fnp(Problem q) {
Certificate c, begin, end; // Declare the certification data variab
le
begin= begin_certificate(q); // begin is the first certification da
ta
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 pol
ynomial
// 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 analy sis,
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 verific
ation
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 mach ines,
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 straightforwar
d and lengthy, and
not very important to most people. Since there are already thousa
nds
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 subpro blems
q1<v,C1>, q2<v,C2), where C = C1?C2.
Proof: The certification dataset can be recursively partitioned as follo
ws:

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 numb
er of
// certificates are roughly the sam
e.
return banp(q1) || banp(q2); // Compute the subproblems respect ively
}

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
problem q, denoted as q = q1 ? q2. The certification datas
et C and the
verification function v of q are defined as follows:

C = C1 ? C2 // C1 and C2 are the certification dataset
s of q1 and q2
// respectively

bool v(x) {
return v1(x) || v2(x); // v1 and v2 are the verification function
s 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 t
o
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 prob lems.
if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes su bproblem
// 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 subproble
m q1
// is valid for any problem q.
}
bool rv=banp2_i(q2,I); // Solve q2 with given information I, ef fective
// regardless of the source of the problem
.
write_ibuf2(ibuf,q);
return rv;
}

The above `banp2_i` does not care which ANP problem (including trivia
l
problems) the given information `I` originates from. The `I` generate
d can
also provide auxiliary information for almost all other ANP problems.

Since the auxiliary information I obtained from the trivial subproble
ms
cannot provide sufficient information to accelerate computation to th
e
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?


--- PyGate Linux v1.5.1
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

The script of proof is formal enough to submit to professional institute, I
think.
Anything unclear or defect?

The following is form https://sourceforge.net/projects/cscall/files/MisFile s/PNP-proof-en.txt/download

--------------------------------------------------------------------------- -----
Algorithmic Problem::= A computer problem in which the computational step
s are a
function of the problem statement's length (size). This problem can be
described asymptotically as the relationship between the problem size a
nd
the computational steps.

Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecut
ive,
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 i
nto
computation problem B by a Ptime procedure, denoted as AóB (bec
ause 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 sol
ve in
O(2^|q|) steps using the following fnp algorithmic 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 do
es
// 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 b
y the
// problem.
bool v(Certificate c);

bool fnp(Problem q) {
Certificate c, begin, end; // Declare the certification data variab
le
begin= begin_certificate(q); // begin is the first certification da
ta
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 pol
ynomial
// 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 analy sis,
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 verific
ation
function, and C = certification dataset (description).

[Note] Also testified by Church-Turing conjecture, no formal language c
an
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 mach ines,
and as a formal language for knowledge or proof.

Prop1: ANP = ??
Proof: ?? ? ANP and ANP ? ??
??, therefore ANP=??
(The proof of the equivalence of ANP and the traditional
Turing machine definition of ?? is straightforwar
d and lengthy, and
not very important to most people. Although the definition of ANP
does
not depend on NDTM theory, there are thousands of real-world ?
????
problems available for verification and reference)

Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subpro blems
q1<v,C1>, q2<v,C2), where C = C1?C2.
Proof: The certification dataset can be recursively partitioned as follo
ws:

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 numb
er of
// certificates are roughly the sam
e.
return banp(q1) || banp(q2); // Compute the subproblems respect ively
}

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
problem q, denoted as q = q1 ? q2. The certification datas
et C and the
verification function v of q are defined as follows:

C = C1 ? C2 // C1 and C2 are the certification dataset
s of q1 and q2
// respectively

bool v(x) {
return v1(x) || v2(x); // v1 and v2 are the verification function
s 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 (A very direct semantic of 'equivalence')

Prop5: For ??? subproblems q1<v,C1> and q2<v,C2> (s
ame 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: Since ??? is the most complex class of
?? problems, by the definition
of ANP, the order of card(C) of the ??? prob
lem must be of order O(2^|q|)
no lower (any lower, ANP/?? problem cannot be comple
tely reduced).
We can add an AuxInfo object called 'auxiliary information' to banp
to
store the results after calculating a certain ???
?? problem q, and rewrite
it as banp2. Depending on the content of the auxiliary information,
banp2 can represent possible algorithms for ANP/??
? problems with
complexities 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);// q can only be reduced to ??
??? subproblems
// q1 and q2.
// card(C1) and card(C2) are roughly equ
al.
AuxInfo I; // I stores information to help solve prob lems.
if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes su bproblem
// q1 and stores any auxiliary information
// that can be derived from q1 into I.
write_ibuf1(ibuf,q); // Write auxiliary information
return true; // The information obtained from subproble
m q1
// is valid for any problem q.
}
bool rv=banp2_i(q2,&I); // Solve q2 with given information I of
which
// any source is effective for q2.
write_ibuf2(ibuf,q);
return rv;
}

[Note] From banp2(q1,&I), we know that the auxiliary information I is
only
meaningful if it contains information related to the certifica tion
dataset C1 of problem q1. This is because if it is not related
, the
computation of other subproblems can generate the auxiliary
information by itself.

The above `banp2_i` does not care which ANP problem (including trivia
l
problems) the given information `I` originates from. The `I` generate
d can
also provide auxiliary information for almost all other ANP problems.

Since the auxiliary information I obtained from computing a fixed
subproblem (including trivial problem) cannot provide sufficient
information to accelerate computation to the extent of improving the
complexity order for any other subproblem (would require infinite spa
ce/
time), the proposition is thus proved (this proof also demonstrates t
hat
the complexity of the ??? problem is O(2^N)).

Conclusion: According to Proposition 5, the certification data for the ?
????
problem are basically independent and must be tested one by one. Sinc
e the
??? problem has O(^|q|) certification data, t
he complexity of the ???
problem is O(2^N), therefore ????. --------------------------------------------------------------------------- ----



--- PyGate Linux v1.5.2
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

The claim is changed to "NPC is O(2^N)" which is stronger than "P!=NP".
The idea of reduction is removed.

The following is form https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow nload

---------------------------------------------------------------------------
--
Algorithmic Problem::= A computer problem in which the computational step
s are a
function of the problem statement's length (size). This problem can be
described asymptotically as the relationship between the problem size a
nd
the computational steps.

Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecut
ive,
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.

ANP::= {q| q is a statement of a decision problem that a computer can sol
ve in
O(2^|q|) steps using the following fnp algorithmic 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 do
es
// 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 b
y the
// problem.
bool v(Certificate c);

bool fnp(Problem q) {
Certificate c, begin, end; // Declare the certification data variab
le
begin= begin_certificate(q); // begin is the first certification da
ta
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 pol
ynomial
// 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 analy sis,
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 verific
ation
function, and C = certification dataset (description).

[Note] Also testified by Church-Turing conjecture: No formal language c
an
surpass the expressive power of a Turing machine (or algorithm, i.e.,
the decisive operational process from parts to the whole). C lan guage
can be regarded as a high-level language of Turing machines, and
as
a formal language for knowledge or proof.

Prop1: ANP = ??
Proof: ?? ? ANP and ANP ? ??
??, therefore ANP=??
(The proof of the equivalence of ANP and the traditional
Turing machine definition of ?? is straightforwar
d and lengthy, and
not very important to most people. Although the definition of ANP
does
not depend on NDTM theory, there are thousands of real-world ?
????
problems available for verification and reference)

Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subpro blems
q1<v,C1>, q2<v,C2), where C = C1?C2.
Proof: The certification dataset can be recursively partitioned as follo
ws:

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 numb
er of
// certificates are roughly the sam
e.
return banp(q1) || banp(q2); // Compute the subproblems respect ively
}

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
problem q, denoted as q = q1 ? q2. The certification datas
et C and the
verification function v of q are defined as follows:

C = C1 ? C2 // C1 and C2 are the certification dataset
s of q1 and q2
// respectively

bool v(x) {
return v1(x) || v2(x); // v1 and v2 are the verification function
s of
// q1 and q2 respectively
}

Therefore, we have the identity: q1<v1,C1>? q2<v2,C2> = q<
v1||v2, C1?C2>
(The algebraic operation rules for '?' are the same as thos
e for
addition in arithmetic).

Prop4: ?=?? iff the algorithm fnp in the ?
?? definition (or ??? algorithm) can be
replaced by a Ptime algorithm.
Proof: Omitted (A very direct semantic of 'equivalence')

Prop5: For ??? subproblems q1<v,C1> and q2<v,C2> (s
ame v, but not required), if
C1 ï C2 = ?, then there is no information in probl
em q1 that is
sufficient in terms of order of complexity to speed up the computati
on
of q2. I.e. the certification data of the ???
? problem are each, in the
sense of computation, equivalently independent.
Proof: Since ??? is the most complex class of
?? problems, by the definition
of ANP, the order of card(C) of the ??? prob
lem must be of order O(2^|q|)
,no lower.
We can add an AuxInfo object called 'auxiliary information' to banp
to
store the results after calculating a certain ???
?? problem q, and rewrite
it as banp2.
Depending on the content of the auxiliary information, banp2 can
represent possible algorithms for ANP/??? pr
oblems with complexities
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);// The split function only requres Ptime
// conversion from q to ??
?? subproblems q1,q2,
// others are non-issue.
AuxInfo I; // I stores information to help solve prob lems.
if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes su bproblem
// q1 and stores any auxiliary information
// that can be derived from q1 into I.
write_ibuf1(ibuf,q); // Write auxiliary information
return true; // The information obtained from subproble
m q1
// is useful? for any problem q.
}
bool rv=banp2_i(q2,&I); // Solve q2 with given information I of
which
// any source is effective? for q2.
write_ibuf2(ibuf,q);
return rv;
}

[Note] From banp2(q1,&I), we know that the auxiliary information I is
only
meaningful to store information related to the certification
dataset C1 of problem q1. This is because if it is not related
, the
computation of other subproblem can generate the auxiliary
information by itself.

The above `banp2_i` does not care which ??? s
ubproblem (including trivial
problems) the given information `I` originates from. The `I` generate
d can
also provide auxiliary information for almost all other ANP problems.

Since the auxiliary information I obtained from computing a fixed
subproblem (including trivial problem) cannot provide sufficient
information to accelerate computation to the extent of improving the
complexity order for any other subproblem (would require infinite spa
ce/
time), the proposition is thus proved.

Conclusion: By Proposition 5, each certification data of the ??
??? problem are
independent in the sense of Ptime verification, the computation is
equivalent to testing them one by one. Since the ??
? problem has O(^|q|)
independent certification data, the complexity of the ??
?? problem is
O(2^N) (???? is proved in the way). ---------------------------------------------------------------------------
--


--- PyGate Linux v1.5.2
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)