> 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.

Great ideas in theoretical computer science