1
$\begingroup$
  1. Define $\Sigma^E_0 = \Pi^E_0=E$,
  2. for every $n>0$, define $\Sigma^E_n=NE^{\Sigma^p_{n-1}}$,
  3. for every $n>0$, define $\Pi^E_n=CoNE^{\Sigma^p_{n-1}}$.

Define the Exponential time hierarchy by $EH=\bigcup_{i\in\mathbb{N}}\Sigma^E_i$. We know that $\Sigma^p_n=\Pi^p_n$ implies $PH=\Sigma^p_n$. My question is whether something like this is true for $EH$ or not.

Q1. Does $\Sigma^E_n=\Pi^E_n$ imply the collapse of the $EH$ to some level? For example, does $E=NE$ imply $EH=E$?

Q2. If we do not know the answer to the above question, Is there any oracle separation? For example is there any oracle $A$ such that $E^A=NE^A$, but $E^A\not={\Sigma^E_2}^A$?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.