From: wyniijj5@gmail.com   
      
   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/fi   
   es/MisFiles/PNP-proof-en.txt/download   
      
   ----------------------------------------------------------------   
   ---------------   
   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 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 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, where v = Ptime verification   
       function, and C = certification dataset (description).   
      
       [Note] Also testified by 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: ℕℙ ⊆ ANP and ANP ⊆ ℕℙ, therefore ANP=ℕℙ   
             (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. 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 can be arbitrarily partitioned into two   
   subproblems   
          q1, q2⊕ q2 = q.   
      
   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 and q2 (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: Since ℕℙℂ is the most complex class of ℕℙ problems, by the   
   definition   
          of ANP, the order of card(C) of the ℕℙℂ problem must be of order   
   O(2^|q|)   
          no lower (any lower, ANP/ℕℙ problem cannot be completely reduced).   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)