# On $NP=\Sigma_2^P$ from non-deterministic time?

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.

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Dec 13 '17 at 7:42
• @D.W. If you did not move the conversation every information would be on one location for people to see. – T.... Dec 13 '17 at 11:27

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.
• 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)$))? – T.... Dec 13 '17 at 11:21
• 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. – Yuval Filmus Dec 13 '17 at 12:20
• 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? – T.... Dec 13 '17 at 22:23