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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Dec 13 '17 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$ – T.... Dec 13 '17 at 11:27
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.

$\endgroup$
  • $\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$ – T.... Dec 13 '17 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 Dec 13 '17 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$ – T.... Dec 13 '17 at 22:23

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.