<p>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$.</p>

<ol>
<li>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.</li>
<li>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$.</li>
</ol>

<p>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?</p>

CC BY-SA 3.0
2013-11-19T01:18:56.127Z
It is immediately contained in PL.
Tayfun Pay
CC BY-SA 3.0
2013-06-02T16:24:01.480Z
(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.
Joshua Grochow
CC BY-SA 3.0
2013-06-04T22:18:11.877Z
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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#mapolylog)), which refers to polylog time.
Robin Kothari
CC BY-SA 3.0
2013-06-04T23:56:14.833Z
Right, I hadn't thought of that. So then maybe "MA$_{logspace}$"?
Joshua Grochow
<cc.complexity-theory><space-bounded><space-complexity>
Non-deterministic logspace with two-sided error
Lior Eldar
# Non-deterministic logspace with two-sided error

(Asked by: username_0 on 2013-06-02)

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?

**Tags:** cc.complexity-theory, space-bounded, space-complexity

> **Comments:**
> **username_2**: (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.  
> **username_3**: 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#mapolylog)), which refers to polylog time.  
> **username_2**: Right, I hadn't thought of that. So then maybe "MA$_{logspace}$"?  
> **username_1**: It is immediately contained in PL.  

---

## 0 answers

