Re: Improved ℙ≠ℕℙ proof

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