3 ms·
Maybe I should have written: "Many have tried to find algorithms in P to solve NP problems and failed to find them." Even now, many people are working on algori
by fjfaase 10mo ago
Maybe I should have written: "Many have tried to find algorithms in P to solve NP problems and failed to find them." Even now, many people are working on algorithms to find solutions for NP problems. I understand that it has been proven that it is not possible to proof P=NP? using 'algorithms'. That might mean that even when a proof is found that P=NP that there still will be no P algorithm to solve NP problems.
- skissane 10mo agoSomeone 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 10mo 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.