Variants of Kannan's Theorem are given where the circuits of
the original theorem are replaced by arbitrary recursively presentable
classes of languages that use advice strings and satisfy certain mild
conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$
does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does
not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ... more >>>

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>