<p>1a) yes by the inclusion.
b) Not sure what you mean by "it". If P=PSPACE then A and B are both in P.</p>

<p>2a) Not necessarily, A could be much easier than B.
b) There are relativized worlds where P=FewP&lt;>NP.
c) No, RP^UP does not necessarily contain NP. Don't confuse UP with Promise-UP. </p>

CC BY-SA 3.0
2012-04-23T01:46:16.227Z
@Fortnow By 1b) If we have a QuasiPolynomial time algorithm for B, then we have shown that QP is in PSPACE and thus P does not equal PSPACE. Since B is contained in CoC=P, then P does not equal CoC=P nor PP. I cannot get the inclusion down to NP though... I do not understand your answer for 2b... I will check the definition of UP and Promise-UP again.. Thank You :)
Tayfun Pay
CC BY-SA 3.0
2012-04-23T11:45:52.303Z
About 2c: Some people choose to define complexity classes such as P, NP, BPP, and UP as classes of promise problems, in which case UP denotes what you write Promise-UP.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-23T14:47:52.980Z
@TayfunPay about 1b) why would $\mathsf{B} \subseteq \mathsf{QP}$ imply that $\mathsf{QP} \subseteq \mathsf{PSPACE}$. It seems to me that the inclusions go the wrong way here. about 2b: Lance is saying that there is an oracle relative to which $\mathsf{P} = \mathsf{FewP}$ and $\mathsf{P} \neq \mathsf{NP}$. so as far we know, the answer to your question is "yes, it can be the case"
Sasho Nikolov
CC BY-SA 3.0
2012-04-23T15:18:26.213Z
@SashoNikolov I see what you mean now.. If B is QP-Complete then that is the case... I do not say that B is QP-Complete. Thanks
Tayfun Pay
CC BY-SA 3.0
2012-04-23T16:48:56.293Z
QP does not have complete problems under polynomial time reductions, as i believe we've discussed before
Sasho Nikolov
CC BY-SA 3.0
2012-04-23T19:32:55.170Z
What is the title of the paper where it shows that there is a relativized worlds where P equals FewP but P does not equal NP. Thanks
Tayfun Pay
CC BY-SA 3.0
2012-04-23T00:57:56.693Z
2012-04-23T00:57:56.693Z
Lance Fortnow
<p>I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance.<br></p>

<p>There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By definition $\mathsf{A}$ $\subseteq$ $\mathsf{B}$ but then it can be easily seen that $\mathsf{A}$ is truth table reducible to $\mathsf{B}$. Furthermore, $\mathsf{B}$ $\subseteq$ $\mathsf{coC_{=}P}$ (<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cocequalsp" rel="nofollow">Zoo</a>) and $\mathsf{FewP}$ $\subseteq$ $\mathsf{A}$ (<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fewp" rel="nofollow">Zoo</a>).<br><br></p>

<p>1)What are the consequences of a Quasi Polynomial Time Algorithm for $\mathsf{B}$ ?<br>
a)Does it put $\mathsf{A}$ in $\mathsf{QP}$ as well?<br>
b)Other than proving that $\mathsf{P}$ $\neq$ $\mathsf{PSPACE}$ and $\mathsf{P}$ $\neq$ $\mathsf{PP}$ does it also show that $\mathsf{P}$ $\neq$ $\mathsf{NP}$?<br><br>
2)What are the consequences of a Polynomial Time Algorithm for $\mathsf{A}$? <br>
a)Does it put $\mathsf{B}$ in $\mathsf{P}$ as well?<br>
b)Since $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{FewP} \subseteq \mathsf{A}$ we will have $\mathsf{P} = \mathsf{UP} = \mathsf{FewP} = \mathsf{A}$ . Then can it still be the case $\mathsf{P}$ does not equal $\mathsf{NP}$? <br>
c)Does it also show that $\mathsf{NP} \subseteq \mathsf{RP}$ since now  $\mathsf{RP}^\mathsf{UP} = \mathsf{RP}$? </p>

CC BY-SA 3.0
2012-04-22T17:16:15.583Z
What is "CoC=P" ? In general, it would be helpful to link to the appropriate class definition in the complexity zoo for the classes you mention, and also use latex math mode, sans serif fonts to mark the classes as is customarily done here.
Suresh Venkat
CC BY-SA 3.0
2012-04-22T18:04:56.007Z
@Suresh I edited in Latex! Here is the link for CoC=P http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cocequalsp
Tayfun Pay
<cc.complexity-theory><soft-question><complexity-classes>
Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P
Tayfun Pay
# Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P

(Asked by: username_0 on 2012-04-22)

I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance.

There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By definition $\mathsf{A}$ $\subseteq$ $\mathsf{B}$ but then it can be easily seen that $\mathsf{A}$ is truth table reducible to $\mathsf{B}$. Furthermore, $\mathsf{B}$ $\subseteq$ $\mathsf{coC\_{=}P}$ ([Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cocequalsp)) and $\mathsf{FewP}$ $\subseteq$ $\mathsf{A}$ ([Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fewp)).

1)What are the consequences of a Quasi Polynomial Time Algorithm for $\mathsf{B}$ ?  
a)Does it put $\mathsf{A}$ in $\mathsf{QP}$ as well?  
b)Other than proving that $\mathsf{P}$ $\neq$ $\mathsf{PSPACE}$ and $\mathsf{P}$ $\neq$ $\mathsf{PP}$ does it also show that $\mathsf{P}$ $\neq$ $\mathsf{NP}$?  
  
2)What are the consequences of a Polynomial Time Algorithm for $\mathsf{A}$?   
a)Does it put $\mathsf{B}$ in $\mathsf{P}$ as well?  
b)Since $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{FewP} \subseteq \mathsf{A}$ we will have $\mathsf{P} = \mathsf{UP} = \mathsf{FewP} = \mathsf{A}$ . Then can it still be the case $\mathsf{P}$ does not equal $\mathsf{NP}$?   
c)Does it also show that $\mathsf{NP} \subseteq \mathsf{RP}$ since now $\mathsf{RP}^\mathsf{UP} = \mathsf{RP}$?

**Tags:** cc.complexity-theory, soft-question, complexity-classes
> **Comments:**
> **username_1**: What is "CoC=P" ? In general, it would be helpful to link to the appropriate class definition in the complexity zoo for the classes you mention, and also use latex math mode, sans serif fonts to mark the classes as is customarily done here.  
> **username_0**: @Suresh I edited in Latex! Here is the link for CoC=P http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cocequalsp  

---

## 1 answers

### Answer by username_2 on 2012-04-23. Score: 6 | Accepted answer

1a) yes by the inclusion.
b) Not sure what you mean by "it". If P=PSPACE then A and B are both in P.

2a) Not necessarily, A could be much easier than B.
b) There are relativized worlds where P=FewP<>NP.
c) No, RP^UP does not necessarily contain NP. Don't confuse UP with Promise-UP.

> **Comments:**
> **username_0**: @Fortnow By 1b) If we have a QuasiPolynomial time algorithm for B, then we have shown that QP is in PSPACE and thus P does not equal PSPACE. Since B is contained in CoC=P, then P does not equal CoC=P nor PP. I cannot get the inclusion down to NP though... I do not understand your answer for 2b... I will check the definition of UP and Promise-UP again.. Thank You :)  
> **username_3**: About 2c: Some people choose to define complexity classes such as P, NP, BPP, and UP as classes of promise problems, in which case UP denotes what you write Promise-UP.  
> **username_4**: @TayfunPay about 1b) why would $\mathsf{B} \subseteq \mathsf{QP}$ imply that $\mathsf{QP} \subseteq \mathsf{PSPACE}$. It seems to me that the inclusions go the wrong way here. about 2b: Lance is saying that there is an oracle relative to which $\mathsf{P} = \mathsf{FewP}$ and $\mathsf{P} \neq \mathsf{NP}$. so as far we know, the answer to your question is "yes, it can be the case"  
> **username_0**: @SashoNikolov I see what you mean now.. If B is QP-Complete then that is the case... I do not say that B is QP-Complete. Thanks  
> **username_4**: QP does not have complete problems under polynomial time reductions, as i believe we've discussed before  
> **username_0**: What is the title of the paper where it shows that there is a relativized worlds where P equals FewP but P does not equal NP. Thanks  

---

