12
$\begingroup$

The class BPL is the set of all problems solvable by a Turing machine running in logarithmic space and polynomial time with two-sided error; that is, if $x\in L$ then the machine accepts with probability at least $2/3$, whereas if $x\notin L$ it accepts with probability at most $1/3$.

  1. What is the immediate non-deterministic complexity class containing BPL? That is, what is the logarithmic-space analog of MA? It seems that NL cannot suffice in this case, and DSPACE($\log^2(n)$) seems too far away up the ladder.
  2. Can one define this class using the following? We have a read-once "witness" tape of polynomial size, a read-once "random" tape of polynomial size, a read-only input tape, a write-only output tape, and a read-write logarithmic-size work tape. The verifier then has to decide with completeness/soundness error at most $1/3$.

At first sight, this might seem reasonable. Yet, unfortunately it already contains iterated multiplication of integer matrices (which is complete for the class DET): Given a matrix $A$, compute $A^n$: We simply ask the prover to provide the sequence of matrices $A,A^2,...,A^n$, we then randomly choose a matrix $A^i$, and verify that $A^i = A^{i-1} \cdot A$, which can be done in logspace. Hence, the question is, is the bounded-error class simply "not-interesting" in the restricted memory model, because it seems to group together space-"hard" with space-"easy" problems?

$\endgroup$
  • 1
    $\begingroup$ (1) I agree that NL isn't the "right" class for the job - NL is to BPL as NP is to BPP, but what you want is something more like MA or AM. (2) Seems like a reasonable definition to me! I haven't seen this class named before, but I'd think something like $MA_{log}$ (or $AM_{log}$, depending on order) or $BP \cdot NL$ would be an appropriate name. $\endgroup$ – Joshua Grochow Jun 2 '13 at 16:24
  • 1
    $\begingroup$ Since $\mathrm{MA}_\mathrm{exp}$ stands for MA with exponential time, someone may confuse $\text{MA}_\text{log}$ to be MA with logarithmic time. There's also $\text{MA}_\mathrm{POLYLOG}$ (see here), which refers to polylog time. $\endgroup$ – Robin Kothari Jun 4 '13 at 22:18
  • $\begingroup$ Right, I hadn't thought of that. So then maybe "MA$_{logspace}$"? $\endgroup$ – Joshua Grochow Jun 4 '13 at 23:56
  • $\begingroup$ It is immediately contained in PL. $\endgroup$ – Tayfun Pay Nov 19 '13 at 1:18

Your Answer

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

Browse other questions tagged or ask your own question.