4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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$
    – Suresh Venkat
    Apr 22, 2012 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, 2012 at 18:04

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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, 2012 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$
    – Tsuyoshi Ito
    Apr 23, 2012 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$
    – Sasho Nikolov
    Apr 23, 2012 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, 2012 at 15:18
  • $\begingroup$ QP does not have complete problems under polynomial time reductions, as i believe we've discussed before $\endgroup$
    – Sasho Nikolov
    Apr 23, 2012 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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