News for hackers. Stuff that matters.

A comment on P = NP Proofs: Advice to claimers. Parent comment

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:

> https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...

[ 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 ]