Improved ℙ≠ℕℙ proof

[wij]

The P!=NP proof should be completed.
The updated proof may even be shorter, intuitive and robust !!!
---------------------------------------------------------------


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(q):

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(q) 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
}

Assume solving some ANP problem by temp_anp(q) whose size-1-subproblem
temp_anp(q1) is solved, then the remaining task has one more information I
(i.e. whatever the computaion of temp_anp(q1) can provide) to reduce the
workload of solving the remaining task, and defined as solve_remain(q2,I).
If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
a O(2^N) level of complexity contradicting he assumed Ptime. Therefore, ℙ≠ℕℙ.
-----------------------------------------------------------------------------

[wij]

Post by wij
The P!=NP proof should be completed.
The updated proof may even be shorter, intuitive and robust !!!
---------------------------------------------------------------
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
   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(q) 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.
          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
          }
Assume solving some ANP problem by temp_anp(q) whose size-1-subproblem
temp_anp(q1) is solved, then the remaining task has one more information I
(i.e. whatever the computaion of temp_anp(q1) can provide) to reduce the
workload of solving the remaining task, and defined as solve_remain(q2,I).
If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
a O(2^N) level of complexity contradicting he assumed Ptime. Therefore, ℙ≠ℕℙ.
-----------------------------------------------------------------------------

A typo in the last paragraph:


Assume solving some ℕℙℂ problem by temp_anp(q) whose size-1-subproblem
temp_anp(q1) is solved, then the remaining task has one more information I
(i.e. whatever the computaion of temp_anp(q1) can provide) to reduce the
workload of solving the remaining task, and defined as solve_remain(q2,I).
If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
a O(2^N) level of complexity contradicting the assumed Ptime. Therefore, ℙ≠ℕℙ.

[wij]

On Mon, 2024-06-03 at 23:05 +0800, wij wrote:


ℙ≠ℕℙ Proved. https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
...[cut]
Note: Another super short proof that ℙ≠ℕℙ (might be less constructive).
Proof: If ℙ=ℕℙ, then ℕℙℂ=ℙ. All the problems in ℕℙ are Ptime reduciable.
That means all the proofs that prove "Decide whether or not a given
number is even" is not a ℕℙℂ are false proofs. Since such proofs are
considered valid, ℕℙℂ and ℙ is not the same, therefore, ℙ≠ℕℙ.

[Bonita Montero]

Philosophizing makes you confused.

[wij]

Post by Bonita Montero
Philosophizing makes you confuse

P!=NP is easy to understand for programmers.
Theory-making (academic) people get confused. I think in pragmatic way.

-----------------------
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

-----------------------------------------------------------------------------
...[cut]
Prop2: ℙ≠ℕℙ
Proof: The temp_anp(q) can be re-written 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 to
// disjoint subproblem q1, q2.
Info I; // I=info. that helps solving q
if(temp_anp_i(q1,I)==true) { // temp_anp_i(q1,I) solves temp_anp(q1)
// and stores whatever helpful into I
return true;
}
return solv_remain(q2,I); // Solve temp_anp(q2) with the given I
}

For simplicity, assume this temp_anp(q) computes a ℕℙℂ problem. If
ℙ=ℕℙ, then information I is unnecessary for solv_remain(q2,I) because
it can compute I in Ptime by its own. Thus, the complexity of
solv_remain(q2,I) is equivalent to the independent size-1-subproblem
temp_anp(q2) (if not equivalent, the general recursive algorithms of
solving ℕℙℂ and Prop1 are wrong, which is not the fact). Equally,
temp_anp_i(q1,I) is then equivalent to the size-1-subproblem
temp_anp(q1) simply by not providing I. Therefore, the complexity of
temp_anp(q) is W(|q|)= W(|q|-1)+W(|q|-1)= 2^(|q|-1)*W(1), W(1)>=1,
a O(2^N) level of complexity contradicting the assumed Ptime.
Therefore, from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ.

IOW, for a ℕℙℂ problem, if the algorithm for one size-1-subproblem
(complexity is irrelevant) does not provide information for another,
(the remaining) size-1-subproblem, then the algorithm solving the ℕℙℂ
problem must take at least O(2^N) steps.
-----------------------------------------------------------------------------