News for hackers. Stuff that matters.

A comment on A Solution of the P versus NP Problem?. Parent comment

Re:A Solution of the P versus NP Problem? by alderz on Monday August 14, 2017 @08:00PM (#15014167)
How does the paper of Hauptmann prove P != NP?

Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP.

Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.

[ Parent | on HN ]
Re:A Solution of the P versus NP Problem? by modalduality on Monday August 14, 2017 @08:05PM (#15014197)
P = NP implies the polynomial hierarchy collapses, thus P = Sigma2, so by contradiction P != NP.
[ Parent | on HN ]