Re: Improved ℙ≠ℕℙ proof

On Fri, 2024-05-31 at 19:50 +0200, immibis wrote:

On 31/05/24 17:07, wij wrote:

This file is intended a proof that ℙ≠ℕℙ.. The contents may be updated anytime.

 
But you can't prove that this is the fastest way to solve the problem.
 

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

The definition already says the loop is iterated O(2^N) times for certificate.
Such thing is categorized as 'intuition' which do not need to prove.