News for hackers. Stuff that matters.
Re:P ≠ NP by lulin on Sunday August 08, 2010 @04:11PM (#1586036)
If I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.
Re:P ≠ NP by faboo on Sunday August 08, 2010 @09:53PM (#1586745)
It isn't actually _necessary_ for a P=NP proof to be constructive. A constructive proof would probably be easier to reason through, but it is prossible to prove the existence of an algorithm without providing one.
Re:P ≠ NP by btilly on Sunday August 08, 2010 @10:33PM (#1586828)
Not so. Pure existence proofs can be non-constructive.

The first historical example of an important proof which was non-constructive was Hilbert's Basis Theorem in 1888, which solved a famous problem posed by Paul Gordon. It is now viewed as in some sense being the first salvo in the debate over constructivism in the 20th century. See http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.