0
$\begingroup$

The assumption $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ seems to yield nothing interesting at all. Is that true?

$\endgroup$
0
$\begingroup$

Yes, we have to admit so. For other normal complexity class $\mathcal{C}$,

either $\mathcal{C}\subseteq \mathrm{PSPACE}$ then we have an interactive protocol with the prover to be replaced by the circuit,

or $\mathcal{C} = \mathrm{EXP}$ in this case, we utilize Meyer's to put $\mathcal{C}$ in $\Sigma_2^p\cap \Pi_2^p \subseteq \mathrm{PSPACE}$ to get back to the previous case.

But in the case of $\mathrm{SUBEXP}$, nothing above applies.


Note that in Meyer's, we have to simulate the machine deciding $\mathrm{L}\in \mathcal{C}$. But as every particular machine $\mathrm{M}$ deciding $\mathrm{L}$ runs in exponential time ($\mathrm{L}$ has infinitely many machines with ever decreasing running time bounds), we cannot have a multi-output circuit for it.

$\endgroup$

Your Answer

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