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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.