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

  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22 '12 at 17:16
  • $\begingroup$ @Suresh I edited in Latex! Here is the link for CoC=P qwiki.stanford.edu/index.php/Complexity_Zoo:C#cocequalsp $\endgroup$
    – Tayfun Pay
    Apr 22 '12 at 18:04

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.

  • $\begingroup$ @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 :) $\endgroup$
    – Tayfun Pay
    Apr 23 '12 at 1:46
  • $\begingroup$ 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. $\endgroup$ Apr 23 '12 at 11:45
  • $\begingroup$ @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" $\endgroup$ Apr 23 '12 at 14:47
  • $\begingroup$ @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 $\endgroup$
    – Tayfun Pay
    Apr 23 '12 at 15:18
  • $\begingroup$ QP does not have complete problems under polynomial time reductions, as i believe we've discussed before $\endgroup$ Apr 23 '12 at 16:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.