1

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). ?

TheoryQuest1
  • 811
  • 5
  • 13
  • 2
    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. – TheoryQuest1 Mar 18 '15 at 17:20
  • 2
    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. – Andy Drucker Mar 18 '15 at 17:43
  • 1
    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. – Andy Drucker Mar 18 '15 at 17:50
  • 1
    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.

    1. 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.
     – TheoryQuest1 Mar 18 '15 at 18:02
  • 5
    @TheoryQuest1 Check out this question http://cstheory.stackexchange.com/questions/21026/consequences-of-np-pspace – Tayfun Pay Mar 18 '15 at 18:57
  • 1
    @TheoryQuest1 Yes, I believe the exponential classes will collapse as well, by a standard padding trick. – Sasho Nikolov Mar 18 '15 at 21:36
  • @TayfunPay Thanks a ton. this is the same Q with few more informative answers. learned a bit more. – TheoryQuest1 Mar 19 '15 at 07:20
  • @SashoNikolov thanks for confirming the outcome. – TheoryQuest1 Mar 19 '15 at 07:21

0 Answers0