Let $\{L^c_i\}_{i}$ be an efficient enumeration of languages in $DTime(2^{n^c})$, e.g. clocked TMs. Assume $EXP\not = NEXP$. Let $L$ be an $NEXP$-complete language and therefore not in $EXP$.

There is a diagonal function $f$ such that for all $c$ and $i$: $$f(i,c) \in L^c_i \leftrightarrow f(i,c) \not\in L$$

Can such an $f$ be in $FPH$ or $FEXP$?

Also related to the above question,

Is $S_2+EXP=NEXP$ consistant?



Your Answer

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