3 ms·
Someone might eventually provide a non-constructive proof that P=NP - a proof that such an algorithm must exist but which fails to actually produce one. Or eve
by skissane 11mo ago
Someone might eventually provide a non-constructive proof that P=NP - a proof that such an algorithm must exist but which fails to actually produce one.
Or even a galactic algorithm-an algorithm for solving an NP-complete problem that is technically in P, but completely useless for anything in practice, e.g. O(n^10000000)
- IAmBroom 11mo ago> solving an NP-complete problem that is technically in P, but completely useless for anything in practice So it's P and NP. (Edit: I keep misphrasing this!) P ?= NP is not about ease, nor even realistic efforts.