Sujet : Re: Improved ℙ≠ℕℙ proof
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theoryDate : 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.