Re: Improved ℙ≠ℕℙ proof

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.