alt Hacker NewsModule 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.”
My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case.
I suspect the answer to BANKACCOUNT=?1_000_000 is “no”, but although my card stops working every month, it starts working again on the last Friday of the month! My research team and I hope to visit an ATM one day to prove my bank balance is meager but until then it remains an open question (albeit likely false) in Gorgoiler Science.
Replies
> Module 8 is worded in a way that surprised me: “if we could decide the languages in NP efficiently, this would lead to amazing applications.”
> My understanding of P=?NP is that all intuition points to the answer being “no”. The openness of the question doesn’t give us hope that a magical algorithm might one day arrive. It just means that despite a lot of suspicion that NP cannot be solved in polynomial time, we cannot yet prove this to be the case.
I admit that I am slightly biased towards that P=NP does indeed hold. I know that this is a non-mainstream view; even though I could give arguments to actual experts in the field that (surprisingly) did convince them that it is much less "clear" than they thought all the time that P \neq NP "must" hold.
On the other hand, I consider it to be plausible that the fastest algorithm that might exist for a "natural" NP-complete problem (e.g. 3-SAT) that exists could have a runtime of \Theta(n^(2^(2^(2^1000000)))).
Or, it is also possible that the proof of P=NP might be highly non-constructive, and obtaining an actual algorithm from this non-constructive proof might be even harder than proving P=NP. Such a situation actually exists in the Robertson-Seymour theorem ("every family of graphs that is closed under taking minors can be defined by a finite set of forbidden minors"):
> https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...
Unluckily,
> https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...
"The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph H, there is a polynomial time algorithm for testing whether a graph has H as a minor. [...] As a result, for every minor-closed family F, there is polynomial time algorithm for testing whether a graph belongs to F: check whether the given graph contains H for each forbidden minor H in the obstruction set of F.
However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it."
So, it is in my opinion a very "religious" belief that even if we could prove P=NP, a practically relevant algorithm will arise from this proof.
There were surprising results in computational complexity before. We can't prove that P /= PSPACE which should be much easier to prove and yet people are stuck on trying to prove P /= NP. Personally I don't think that P = NP and if it were it would be very surprising, but "very surprising" in not "out of the question".