0
$\begingroup$

Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.


For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.

$\endgroup$
0
$\begingroup$

Yes, I can.

First of all, $\mathrm{poly}(\mathrm{subexp}) = \mathrm{subexp}$. So, we can simulate a subexp TM in subexp time. (This is in stark contrast to standard $\mathrm{SUBEXP}$ where we do not have any particular subexp machine)

Using this, we are able to put $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$. The poly space TM would try every possible poly-size circuit and for each circuit make $2^n \times 2^n$ local checking of the tableaux using the current circuit. Note that the subexp TM never touches the $2^n$th cell and would cease to run long before $2^n$ time but that does not affect the poly space bound.

After putting $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$, we use the result of interactive proving protocol with the power of the prover at most $\mathrm{P}^\mathrm{L}$ (where $\mathrm{L}$ is the language at hand) to push it down to $\mathrm{MA}$.

$\endgroup$

Your Answer

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