<p>Is there a classification of problems based on
how much <em>additional</em> memory (other than input) they would need?</p>
<p>For context: assume we have a multi-tape Turing machine <span class="math-container">$M$</span>,
with a bounded input tape and a <em><strong>memory</strong></em> tape.
The input tape is bounded by the input size.
Any extra memory that <span class="math-container">$M$</span> needs to use
(other than its control automaton)
should only be read from and written on the memory tape.</p>
<p>Given a bound <span class="math-container">$b(n)$</span>, where <span class="math-container">$n$</span> is the input size,
what kinds of problems can <span class="math-container">$M$</span> solve such that,
<span class="math-container">$M$</span> uses at most <span class="math-container">$b(n)$</span> many 'cells' (or bits) of its memory tape?
I'm mainly interested in the cases
where <span class="math-container">$b$</span> is constant or depends logarithmically on <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2024-09-16T08:40:52.840Z
What does it mean formally that any variables must be read and written on the memory tape? How exactly do you force that the work tape is not used to store temporary data?
Vladimir Lysikov
CC BY-SA 4.0
2024-09-16T09:08:46.993Z
@VladimirLysikov you're right! Please read the edited version.
Mahyar
CC BY-SA 4.0
2024-09-16T09:14:40.857Z
Doesn't the usual definition of space-bounded classes look exactly like that? For example, see §4.1 in Arora-Barak, the definition uses a machine with a read-only input tape and counts the space used on other tapes.
Vladimir Lysikov
CC BY-SA 4.0
2024-09-16T09:17:31.280Z
@VladimirLysikov I didn't know where to look or read. Thanks for the reference!
Mahyar
CC BY-SA 4.0
2024-09-16T09:26:11.613Z
This is just the standard definition of space complexity. In particular, logarithmic space is [L](https://complexityzoo.net/Complexity_Zoo:L#l), and constant space is [REG](https://complexityzoo.net/Complexity_Zoo:R#reg).
Emil Jeřábek
<cc.complexity-theory><turing-machines><space-bounded>
Problem classes based on additional memory
Mahyar
# Problem classes based on additional memory

(Asked by: username_0 on 2024-09-16)

Is there a classification of problems based on
how much *additional* memory (other than input) they would need?

For context: assume we have a multi-tape Turing machine $M$,
with a bounded input tape and a ***memory*** tape.
The input tape is bounded by the input size.
Any extra memory that $M$ needs to use
(other than its control automaton)
should only be read from and written on the memory tape.

Given a bound $b(n)$, where $n$ is the input size,
what kinds of problems can $M$ solve such that,
$M$ uses at most $b(n)$ many 'cells' (or bits) of its memory tape?
I'm mainly interested in the cases
where $b$ is constant or depends logarithmically on $n$.

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

> **Comments:**
> **username_1**: What does it mean formally that any variables must be read and written on the memory tape? How exactly do you force that the work tape is not used to store temporary data?  
> **username_0**: @VladimirLysikov you're right! Please read the edited version.  
> **username_1**: Doesn't the usual definition of space-bounded classes look exactly like that? For example, see §4.1 in Arora-Barak, the definition uses a machine with a read-only input tape and counts the space used on other tapes.  
> **username_0**: @VladimirLysikov I didn't know where to look or read. Thanks for the reference!  
> **username_2**: This is just the standard definition of space complexity. In particular, logarithmic space is [L](https://complexityzoo.net/Complexity_Zoo:L#l), and constant space is [REG](https://complexityzoo.net/Complexity_Zoo:R#reg).  

---

## 0 answers

