New answers tagged

0

Your definition of EXP is a bit off (you're thinking of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$ instead of $\textbf{EXP} = \textbf{DTIME}(2^{n^{O(1)}})$), but either way the assertion that "each oracle would itself solve an exponential time problem in a single step" is false. This is because, given exponential time, the machine can write (say) $2^n$ bits to ...


1

Let me answer your questions one by one. Black-box separations versus oracle separations Black-box algorithms are given access to a black box. For example, an algorithm might get black box access to a function $f\colon \{0,1\}^n \to \{0,1\}$. This means that the algorithm can obtain the value of $f(x)$ for any given $x \in \{0,1\}^n$, but is not otherwise ...


Top 50 recent answers are included