Re: Improved ℙ≠ℕℙ proof

On 1/06/24 00:33, wij wrote:

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.
 

But there could be a faster way to find the certificate.
Example:
bool v(unbounded_integer c) {return c*c == 40000;}
You could use 201 iterations to find that v(200) is true, and that would be O(2^N) with N being the problem length. But you could also look inside the function v, and see that the problem is calculating the square root of a certain number, and then you could calculate the square root of that number. The problem is in NP, but it's also in P because there's a faster solution. So you can't prove that problems aren't in P this way.