Improved ℙ≠ℕℙ proof

[wij]

This proof is quite direct and may be too easy to many. But proof is proof
The good thing is that this proof suggests a general method for problem complexity,
easy to (false) verify by reviewers. Any comments?

This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

This proof suggests a general algorithm for problem complexity, easy to false
prove. With lots of algorithms out there, I only know a few of them, thus,
cannot effectively verify the proof. And, the details of this proof are many
and basic, concise description should be sufficient.

-----------------------------------------------------------------------------
Algorithmic problem::= Problems that can processed by asymptotic analysis.

ANP::= Another NP is a set defined as {q| q is a description of the algorithmic
decision problem that provides 1. A set of certificate data C 2. A Ptime
(Polynomial time) verification method v 3. The answer of q is 'yes' iff
there exists a certificate c, c∈C, such that v(c) is true 4. q can be
computed within O(2^|q|) steps. }.
More precisely, ANP is the set of problems that can be solved by the
following pseudo-C/C++ program temp_anp(n):

bool temp_anp(Problem q) { // Problem: Description of the problem
Certificate c,begin,end; // Certificate data can be accessed by
begin= get_begin_certificate(q); // iteration, at least.
end = get_end_certificate(q);
for(c=begin; c!=end; c=next(c)) { // O(2^|n|) loop (see Note2)
if(v(c)) return true; // v:Certificate->{true,false}, Ptime
// verification function.
}
return false;
}

Note1: Relative to the Turing Machine language for ℕℙ, the reason using
pseudo-C/C++ is that 1.C-code (almost all high level programming
language not involving special hardware features) and TM language are
computationally interchangable. 2.It describes the problem more clearly
(but not always) 3.The result 'false' is visible 4. ℕℙ definition does
not say the certificate C and the verication v are given, fixed
arguments. In ANP, v(c) is explicitly spedified a Ptime function
5.Easier for machine aided verification.

Note2: The semantics of the for loop in temp_anp(n) includes nested loops for
sets like C=C1×C2×C3×...

Theorem: Sequential execution of O(P) number of Ptime functions is equivalent to
the execution of one single Ptime function.

Lemma1: If ANP=ℙ, then there exists a Ptime recursive algorithm (which normally
contains only one recursive call) equivalent to temp_anp(..).
Proof: The number of certificate data to infer in temp_anp(..) is O(2^|q|).
If ANP=ℙ, then there exists an Ptime algorithm which only need to
actually executes O(P) number of verification v(c) and performs the
equivalent function of what the O(2^|q|) loop does. IOW, each execution
of the v(c) can in average reduce O(2^N) uncertainties....This is
equivalent to say that one Ptime computation can reduce the problem size
(normally by 1). Then, what the smaller size problem left can be solved
by a recursive call.

Lemma2: Assuming an ANP problem q is analysized by a recursive method and a
recursive call has completed its task of solving the subproblem (of
size= |q|-1). If the workload of what is left can be described as
solving a subproblem, then, problem q can only be solved in O(2^N) steps
, i.e. q∉ℙ.
Proof: If the workload of what is left (denoted as W(|R|) from removing the
assumingly solved subproblem is equivalent to the workload of solving R
as a recursive subproblem, then, the workload of problem q is determined
as (assume m1=|q|-1) O(2^m1)+O(2^m1)= O(2^|q|), regardless of 'possibly
other algorithm' because the workloads are all the same described as
solving a recursive subproblem.
If the workload of what is left (i.e. R) is not equivalent to the
workload of solving R as another subproblem, the workload of R must be
less than O(2^N) steps (otherwise, it msut be solvable as a subproblem).
Therefore, the workload of problem q is W(|q|)= W(|q-1|)+W(|R|)
= |q|*W(|R|), a value less than O(2^N).

Take Subset Sum as example:
bool subset_sum(const UInt* set, UInt n_elem, UInt sum) {
if(sum==0) return true;
if(n_elem==0) return false;

if(set[n_elem-1]>sum) {
return subset_sum(set,n_elem-1,sum);
}
return subset_sum(set,n_elem-1,sum) || // Subproblem that does not
// contain the last element.
subset_sum(set,n_elem-1,sum- set[n_elem-1]);
}

Assuming a subproblem case of subset_sum is completed, the left task is
equivalent to solving another subbproblem. Therefore, Subset Sum∉ℙ.

Several ℕℙℂ instances that are easy to test by Lemma2, e.g. TSP,... can also be
easily deduced only solvable in O(2^N) steps, i.e. ℕℙℂ≠ℙ. Thus, we can conclude
ℙ≠ℕℙ.
-----------------------------------------------------------------------------

[wij]

Woo, the updated proof is even lots shorter (and intuitive?).
-----------------------------------------------------------------------------


This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

-----------------------------------------------------------------------------
Algorithmic problem::= Problems that can be processed by asymptotic analysis.

ANP::= Another NP is a set defined as {q| q is a description of the algorithmic
decision problem that provides 1. A set of certificate data C 2. A Ptime
(Polynomial time) verification method v 3. The answer of q is 'yes' iff
there exists a certificate c, c∈C, such that v(c) is true 4. q can be
computed in at most O(2^|q|) steps. }.
More precisely, ANP is the set of problems that can be solved by the
following pseudo-C/C++ program temp_anp(n):

bool temp_anp(Problem q) { // Problem: Description of the problem
Certificate c,begin,end; // Certificate data can be accessed by
begin= get_begin_certificate(q); // iteration, at least.
end = get_end_certificate(q);
for(c=begin; c!=end; c=next(c)) { // O(2^|n|) loop (see Note2)
if(v(c)) return true; // v:Certificate->{true,false}, Ptime
// verification function.
}
return false;
}

Note1: Relative to the Turing Machine language for ℕℙ, the reason using
pseudo-C/C++ is that 1.C-code (almost all high level programming
language not involving special hardware features) and TM language are
computationally interchangeable. 2.It describes the problem more
clearly (but not always) 3.The result 'false' is visible 4. ℕℙ
definition does not say the certificate C and the verication v are
given, fixed arguments. In ANP, v(c) is explicitly spedified a Ptime
function 5.Easier for machine aided verification.

Note2: The semantics of the for loop in temp_anp(n) includes nested loops for
sets like C=C1×C2×C3×...

Polynomial time procedure::= (or polynomial time function) A procedure composed
of sequential execution of O(P) number of fixed-time procedures.
(Therefore, O(P) number of sequential Ptime procedure is equivalent to a
single Ptime procedure)

Size-1-subproblem::= The problem whose size of input is less by one than that
of the orginal problem.

Theorem: ANP problem can be divided into two size-1-subproblems.
Proof: By spliting the certificate as follow:
bool temp_anp(Problem q) {
if(q.certificate().size()<Thresh) { // Thresh is a small constant
return solve_thresh_case(q);
}
Problem q1,q2;
split_certificate(q,q1,q2); // split the certificate in q
return temp_anp(q1) || temp_anp(q2); // to form q1,q2
}

The proof above also illustrates that ANP is merely a kind of class of problems
that temp_anp can handle independent certificates. I.e. the result of v(c1) and
v(c2) may be completely unrelated. As there are n number of such certificates,
at most such n number of steps are required. This conclusion applies to any
number of n (this view can also be formed by the definition of temp_anp, the
proof just provides another view in subproblems).

Because there are O(2^N) certificates, ANP≠ℙ. If ANP⊆ℕℙ, ℙ≠ℕℙ can be concluded.
-----------------------------------------------------------------------------