2
$\begingroup$

We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$.

  1. Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-deterministic $O((n^k)^c)$ time which is non-deterministic $O(poly(n))$ time)?

  2. Is there a reason we cannot conclude $NP=\Sigma_2^P$ from this?

From this $NP=PH$ should hold.

Improve this question
$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W. ♦
    Commented Dec 13, 2017 at 7:42
  • $\begingroup$ @D.W. If you did not move the conversation every information would be on one location for people to see. $\endgroup$
    – Turbo
    Commented Dec 13, 2017 at 11:27

1 Answer 1

Reset to default
2
$\begingroup$

Here is a simpler "proof" using the same ideas. I will show that NP=coNP. Indeed, suppose that $L \in \mathsf{coNP}$, and consider the machine which on input $x$, invokes the NP-oracle $\overline{L}$, and outputs the opposite value.

What goes wrong in this argument? Let us use the "witness" definition of NP: a language $L$ is in NP if there exist a polynomial $p$ and a polytime predicate $P$ such that $$ x \in L \Longleftrightarrow \exists |y| \leq p(|x|) \, P(x,y). $$ Now suppose that $L$ is in coNP, that is, $$ x \in L \Longleftrightarrow \forall |y| \leq p(|x|) \, \lnot P(x,y). $$ (We get this by applying the previous definition to $\overline{L}$.)

Our machine deciding $L$ nondeterministically accepts as input $x,y$ and outputs $\lnot P(x,y)$. However, this accepts a different language $L'$ given by $$ x \in L' \Longleftrightarrow \exists |y| \leq p(|x|) \, \lnot P(x,y). $$ The difference is the quantification — existential instead of universal.

Informally, this shows that nondeterministic machines cannot simulate nondeterministic oracles. However, they can simulate deterministic oracles: $\mathsf{NP}^L = \mathsf{NP}$ for all polytime $L$. This is because an NP-machine can simulate the computation of $L$ on any given input directly. The same cannot be said about nondeterministic oracles.

Improve this answer
$\endgroup$
3
  • $\begingroup$ OK I have accepted your answer. I will look closely to digest. However your view on these two will help. 1. $P$ is deterministic and can it simulate non-deterministic queries? That is since $NP=\cup_{k\in\Bbb N}NTIME(n^k)$ can we say $P^{NP}$ is also in $\cup_{k\in\Bbb N}NTIME(n^k)$ or is the best containment for $P^{NP}$ just $\cup_{k\in\Bbb N}NTIME(2^{n^k})$ or $NEXP$? 2. Why doesn't $NTIME(f(n))=coNTIME(f(n))$ give $NP=coNP$ (from $\cup_{k\in\Bbb N}NTIME(n^k)=\cup_{k\in\Bbb N}coNTIME(n^k)$))? $\endgroup$
    – Turbo
    Commented Dec 13, 2017 at 11:21
  • 1
    $\begingroup$ The class $\mathsf{P}$ cannot simulate polytime nondeterministic queries (unless $\mathsf{P}=\mathsf{NP}$). Also, $\mathsf{NTIME}(n^k)$ is not known to be equal to $\mathsf{coNTIME}(n^k)$, and indeed these classes are suspected to be different. $\endgroup$
    – Yuval Filmus
    Commented Dec 13, 2017 at 12:20
  • $\begingroup$ So we do not know whether $P^{NP}\subseteq\cup_{k\in\Bbb N}NTIME(2^{(\log n)^k})\subseteq NTIME(SUBEXPTIME)$ while ${NP}=\cup_{k\in\Bbb N}NTIME(n^k)\subseteq \cup_{k\in\Bbb N}NTIME(2^{(\log n)^k})$ correct? $\endgroup$
    – Turbo
    Commented Dec 13, 2017 at 22:23

Your Answer

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

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