Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #105973

Re: Improved ℙ≠ℕℙ proof

Show all headers | View raw

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.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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