Hacker News Reader

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.

View on HN

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)

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

Reply on news.ycombinator.com