Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #105844
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Improved ℙ≠ℕℙ proof |
| Date | 2024-06-01 06:33 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <a1ff30e31597b9760aaa076a3b29748b59e6751f.camel@gmail.com> (permalink) |
| References | <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com> <eed8bcaeee2337a7d842401b4bd6e2e409ddc213.camel@gmail.com> <v3d2km$2b0jm$2@dont-email.me> |
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.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-30 08:24 +0800
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-31 23:07 +0800
Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-05-31 19:50 +0200
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-01 06:33 +0800
Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-06-01 14:47 +0200
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-02 06:18 +0800
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 22:22 +0800
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 23:04 +0800
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-06 12:45 +0800
Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-06-04 16:14 +0200
Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-05 15:33 +0800
csiph-web