Re: Improved ℙ≠ℕℙ proof

Liste des GroupesRevenir à theory 
Sujet : Re: Improved ℙ≠ℕℙ proof
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theory
Date : 01. Jun 2024, 23:18:21
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <e7c3a20a0f0db1665f53adca3c2cd553178cb017.camel@gmail.com>
References : 1 2 3 4 5
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
On Sat, 2024-06-01 at 14:47 +0200, immibis wrote:
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.

"...More precisely, ANP is the set of problems that can be solved by the
   following pseudo-C/C++ program temp_anp(q):..."

All that temp_anp(..) can solve are ANP problems, including a specific subset
of O(2^N) problems.



Date Sujet#  Auteur
30 May 24 * Improved ℙ≠ℕℙ proof11wij
31 May 24 `* Re: Improved ℙ≠ℕℙ proof10wij
31 May 24  +* Re: Improved ℙ≠ℕℙ proof4immibis
1 Jun 24  i`* Re: Improved ℙ≠ℕℙ proof3wij
1 Jun 24  i `* Re: Improved ℙ≠ℕℙ proof2immibis
2 Jun 24  i  `- Re: Improved ℙ≠ℕℙ proof1wij
3 Jun 24  `* Re: Improved ℙ≠ℕℙ proof5wij
3 Jun 24   +* Re: Improved ℙ≠ℕℙ proof2wij
6 Jun 24   i`- Re: Improved ℙ≠ℕℙ proof1wij
4 Jun 24   `* Re: Improved ℙ≠ℕℙ proof2immibis
5 Jun 24    `- Re: Improved ℙ≠ℕℙ proof1wij

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal