4 ms·
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
by lulin 16y ago
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.
- faboo 16y agoIt 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.
- btilly 16y agoNot 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_theorem http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.