Thread · HN Continuity

P vs NP does not mean what people think it means:

- Even if we have P=NP, it is not even known whether there will ever exist a "practically useful/fast" algorithm for solving NP-complete decision problems.

- If P != NP, it is perfectly reasonable that there exists an algorithm that is for all practical purposes "fast" algorithm (say, some O(n^{log log log log log log log n}) algorithm with a very small hidden constant) for solving NP-complete decision problems.

- It is entirely possible that average case complexity is the much more important complexity measure than the worst-time measure that is used for defining the P and NP complexity classes. If you are into this kind of questions, you might enjoy the article

Fifty Years of P vs. NP and the Possibility of the Impossible

<a href="https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/" rel="nofollow">https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the...

and the paper

R. Impagliazzo

A personal view of average-case complexity

<a href="https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf" rel="nofollow">https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf

Also, in the realm of complexity theory, the question of P vs NP is just a small puzzle piece.

Just to give one example: isn't the question of P vs PSPACE much more exciting. If you believe in P != NP, P != PSPACE is a trivial corollary. But we can't even exclude P = PSPACE.

Seriously: there exist so many complexity classes (some of high potential practical importance) for which we often basically know nothing except for the trivial inclusions.