3 Replies - 11074 Views - Last Post: 06 November 2016 - 01:14 PM

#1 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

[News] NP = PSPACE and NP = co-NP

Post icon  Posted 31 October 2016 - 02:52 PM

A paper has been placed on the arXiv, claiming NP = PSPACE and NP = co-NP. These results are quite major in complexity theory! First, recall that NP is the set of languages where if w \in L, we can verify this in polynomial time (for a fixed polynomial). PSPACE is the set of languages that can be decided using a polynomial amount of space. By previous result, we have NP \subset PSPACE.

More details on NP \subset PSPACE:
Spoiler


We define co-NP to be the set of languages where if w is not in L, then this can be verified in polynomial time (for a fixed polynomial). So in particular, if P = NP, then NP = co-NP (as the decider for a language L could be used as the verifier for membership and non-membership). By the contrapositive, if we knew that NP != co-NP, we would have that P != NP. This is why our second result that NP = co-NP is so important.

Note that just because we can efficiently verify membership and non-membership does not mean we can decide in polynomial time. That is, we do not have that P = NP.

Link: https://arxiv.org/pdf/1609.09562v1.pdf

Is This A Good Question/Topic? 4
  • +

Replies To: [News] NP = PSPACE and NP = co-NP

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [News] NP = PSPACE and NP = co-NP

Posted 04 November 2016 - 02:07 PM

I'd really like to ensure that people not get too excited over this. The people that wrote it have no track record of work in complexity theory and proofs like this one come out all the time. The paper makes no mention of the fact that this result would collapse the polynomial hierarchy to NP. Short of P=NP PH=NP (e.g. does the polynomial hierarchy collapse) is probably one of the least believed possibilities in complexity theory. And really this paper is claiming something even a bit more unexpected than that. We'll have to wait for the complexity theorist to get back to us on this. This isn't like the graph isomorphism breakthrough which was expected (correctly) to be right. I'd also claim that they violate some other things to watch out for.

That said this should absolutely be watched! If they're right this is HUGE!!! This would flip our expectations of complexity theory on end! This would be the largest advance in complexity theory sense....ever. This paper should be given a fair chance and carefully reviewed.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

Re: [News] NP = PSPACE and NP = co-NP

Posted 04 November 2016 - 07:23 PM

Our logician (who was a Tarski student) discussed this problem today in our seminar. He is skeptical, as was our complexity theorist. However, they came across a blog on the foundations of mathematics (the link still eludes my Google-fu) in which folks were criticizing the approach but not the technicalities of the paper (i.e., nobody pointed out an explicit fallacy in the paper). Additionally, the authors chimed in and addressed the concerns being presented. It lends some credibility that this paper is worth investigating, and that the authors aren't writing a monthly P = NP paper.
Was This Post Helpful? 1
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [News] NP = PSPACE and NP = co-NP

Posted 06 November 2016 - 01:14 PM

That's highly encouraging actually. Now we wait a few months for the actual experts to look at it and inform us of the result!

...I *HATE* waiting on this
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1