5 ms·
Does having a proof of P=NP necessarily mean that you can write the code to solve NP problems though?
by vermilingua 8y ago
Does having a proof of P=NP necessarily mean that you can write the code to solve NP problems though?
- lisper 8y agoNot necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like.
- sidusknight 8y agoWhat do you image a constructive proof looking like?
- lisper 8y agoIt would look like an algorithm that solves an NP-complete problem in polynomial time. (Isn't that obvious?)
- sidusknight 8y agoSure. And why does that seem any more feasible than a non-constructive proof?
- lisper 8y agoI don't know. Why is the moon plaid?
- wolfgke 8y ago> Not necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like. Have a look at the proof of the Robertson-Seymour theorem. Here the Wikipedia section about its importance in complexity theory: > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=867644170#Polynomial_time_recognition https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...
- lisper 8y agoInteresting. Thanks!