P = NP Proofs: Advice to claimers

Re:P = NP Proofs: Advice to claimers by vermilingua on Monday April 22, 2019 @07:28PM (#19724103)

Does having a proof of P=NP necessarily mean that you can write the code to solve NP problems though?

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by lisper on Monday April 22, 2019 @07:37PM (#19724184)

Not necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like.

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by wolfgke on Monday April 22, 2019 @08:19PM (#19724450)

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

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by lisper on Monday April 22, 2019 @08:42PM (#19724577)

Interesting. Thanks!

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by sidusknight on Monday April 22, 2019 @08:00PM (#19724335)

What do you image a constructive proof looking like?

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by lisper on Monday April 22, 2019 @08:43PM (#19724583)

It would look like an algorithm that solves an NP-complete problem in polynomial time. (Isn't that obvious?)

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by sidusknight on Tuesday April 23, 2019 @09:39AM (#19728422)

Sure. And why does that seem any more feasible than a non-constructive proof?

[ Parent | on HN ]

Re:P = NP Proofs: Advice to claimers by lisper on Tuesday April 23, 2019 @11:22AM (#19729502)

I don't know. Why is the moon plaid?

[ Parent | on HN ]