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

Groups > comp.theory > #106237

Re: Improved ℙ≠ℕℙ proof

Show all headers | View raw

On 3/06/24 16:22, wij wrote:
> If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
> without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
> But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
> a O(2^N) level of complexity contradicting he assumed Ptime. Therefore, ℙ≠ℕℙ.

If I understand it correctly, you think that if an algorithm for solving 
a problem takes O(2^N) complexity then the problem can't be P-time.

But this is not correct. There are slow algorithms for fast problems. 
For example, if I know a binary number M, and I want to calculate 
whether all binary numbers with the same number of bits are less than or 
equal to M, I could do it by looping through all the binary numbers with 
the same number of bits, and checking if each one is less or equal. That 
would be an O(2^N) algorithm. Or, I could think about the problem for a 
bit, and then check whether all the bits in M are 1. That would be an 
O(N) algorithm. Since there is an O(N) algorithm, it is a P-time problem 
- even though an O(2^N) algorithm exists as well.

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