<p>The primary Impact i know would be that:</p>

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

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

CC BY-SA 3.0
2015-03-18T17:20:20.180Z
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
CC BY-SA 3.0
2015-03-18T17:43:17.260Z
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
CC BY-SA 3.0
2015-03-18T17:50:39.250Z
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
CC BY-SA 3.0
2015-03-18T18:02:53.730Z
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.
TheoryQuest1
CC BY-SA 3.0
2015-03-18T18:57:18.550Z
@TheoryQuest1 Check out this question http://cstheory.stackexchange.com/questions/21026/consequences-of-np-pspace
Tayfun Pay
CC BY-SA 3.0
2015-03-18T21:36:39.163Z
@TheoryQuest1 Yes, I believe the exponential classes will collapse as well, by a standard padding trick.
Sasho Nikolov
CC BY-SA 3.0
2015-03-19T07:20:16.847Z
@TayfunPay Thanks a ton. this is the same Q with few more informative answers. learned a bit more.
TheoryQuest1
CC BY-SA 3.0
2015-03-19T07:21:34.793Z
@SashoNikolov thanks for confirming the outcome.
TheoryQuest1
<cc.complexity-theory><complexity-classes><p-vs-np>
What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?
TheoryQuest1
# What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

(Asked by: username_0 on 2015-03-18)

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

**Tags:** cc.complexity-theory, complexity-classes, p-vs-np

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_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.  
> **username_0**: 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.  
> **username_2**: @username_0 Check out this question http://cstheory.stackexchange.com/questions/21026/consequences-of-np-pspace  
> **username_3**: @username_0 Yes, I believe the exponential classes will collapse as well, by a standard padding trick.  
> **username_0**: @TayfunPay Thanks a ton. this is the same Q with few more informative answers. learned a bit more.  
> **username_0**: @SashoNikolov thanks for confirming the outcome.  

---

## 0 answers

