Re:On Norbert Blum’s claimed proof that P does not equal NP
by chx on Thursday August 17, 2017 @01:09AM
(#15033955)
Even if it'll be a constructive proof, it doesn't mean you could actually write the C program. It'll be like, here are the steps to construct an algorithm for this NP complete problem and then the number of steps itself is bound by n^(absurdly large number) and then prove the complexity is bound by n^(another absurdly large number). It will have zero practical consequences.
One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems.
I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".