# Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P

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) and $\mathsf{FewP}$ $\subseteq$ $\mathsf{A}$ (Zoo).

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}$?

• 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. Commented Apr 22, 2012 at 17:16
• @Suresh I edited in Latex! Here is the link for CoC=P qwiki.stanford.edu/index.php/Complexity_Zoo:C#cocequalsp Commented Apr 22, 2012 at 18:04

• @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" Commented Apr 23, 2012 at 14:47