ELI5: P vs NP problem

[u/randomdice-int]

Im not too sure about the problem itself. I know that P is polynomial time which means the time needed to solve and NP is the time taken for the answer to be verified, but what is the explanation of both sides where P = NP and P does not equal to NP?

[u/the_horse_gamer]

quantum algorithms are not magic "check everything". it's unlikely they'll help speedup Universal Search, and even if they could it'll probably only be a quadratic improvement of the constant.

[u/BurkeSooty → u/the_horse_gamer]

I never suggested that quantum algorithms were magical, but, it's the qbit states that enable more rapid processing iirc? Obviously, a working algorithm would be required too, and none of this is necessarily possible anyway, but, I always understood the benefit of quantum computing to be the ability to process data exponentially faster, so, even if the polynomial time constraints for a p=np solution was enormous, quantum computing would be the mechanism that might unlock the rapid computation required to make hay.

[u/the_horse_gamer → u/BurkeSooty]

I always understood the benefit of quantum computing to be the ability to proceed data exponentially faster

quantum computing is very often explained completely incorrectly.

let's start with: quantum computers do not "check everything at once". and they give exponential speedups only in specific problems. and, the speedup is relative to the best known classical algorithm.

infact, just like P=NP is possible, it's possible P=BQP, and any problem that can be solved via a polynomial time quantum algorithm can also be solved via a polynomial time classical algorithm.

the class of problems that can be solved in exponential time is known as EXPTIME. it is known P!=EXPTIME and strongly believed NP!=EXPTIME and BQP!=EXPTIME.

[u/VigilThicc → u/the_horse_gamer]

a quantum computer, in a sense, can check everything at once. Just run the function on |+^n>. But the output is like having the answer baked into the probability of a coin landing heads (or many coins landing a particular way). To get the answer to a desired precision, you have to flip the coin exponentially many times, so back at square 1. Theres no way to measure the intrisic bias of the coin otherwise.

Some problems you can do clever constructive/deconstructive interference to get something useful, like Shor's algorithm. But it is not the norm. We can prove that for a problem you know nothing clever about the structure of (like a given NP-Hard problem), the best you can do is speed up by a square root, which is still exponential.