1
$\begingroup$

The primary Impact i know would be that:

Polynomial Hierarchy collapses to Level 1. NP=co-NP NP=BPP NP=PSPACE BQP=NP and so on..

What are the attack directions it will open for settling P=NP (in the sense that suppose X=Y or X!=Y is proven P=NP or P!=NP). ?

$\endgroup$
8
  • 2
    $\begingroup$ may I also know the reason for the down-votes (i.e. if there is a flaw in the Q). or the Q is unimportant theoretically ? i have doubts regarding that part. much obliged. $\endgroup$ Mar 18 '15 at 17:20
  • 2
    $\begingroup$ There's nothing wrong with your question. As far as we know, it could be that NP = PSPACE; in that case we would still not know whether P = NP. (Indeed, one can build oracle worlds where NP = PSPACE and where P and NP are either the same or different.) The main thing is that almost everyone believes NP and PSPACE are different. And, we fear that this will be very hard to prove, with progress as difficult as on the P vs NP question. $\endgroup$ Mar 18 '15 at 17:43
  • 1
    $\begingroup$ I had a bit of trouble seeing what you meant by "NP/co-NP" although I see now. I'm still not quite sure what you mean by "remaining classes left outside". If NP = PSPACE then, for example, we'd learn that NEXP is a proper superset of PSPACE, which we don't currently know. This is because we know NEXP != NP by the nondeterministic time hierarchy theorem. $\endgroup$ Mar 18 '15 at 17:50
  • 1
    $\begingroup$ Thanks a lot for your reply. Regarding the "remaining classes left outside" the Q was not properly framed, so apologies. What I meant is the following: 1. The classes NEXPTIME and EXPSPACE: In case of 1. does it also prove NEXPTIME and EXPSPACE are same (analogous to NP and PSPACE).If yes then the hirerchy reduces to P (Subset) NP (Subset) EXPTIME (Subset) NEXPTIME. 2. How will it impact Classes left b/w P and NP. - I have doubt they won't be, so P=NP? remains still as hard. $\endgroup$ Mar 18 '15 at 18:02
  • 5
    $\begingroup$ @TheoryQuest1 Check out this question cstheory.stackexchange.com/questions/21026/… $\endgroup$
    – Tayfun Pay
    Mar 18 '15 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.