Questions tagged [space-bounded]

Questions about space resources of computations in computational complexity or algorithms.

Filter by
Sorted by
Tagged with
52
votes
4answers
4k views

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

This might be a subjective question rather than one with a concrete answer, but anyway. In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands ...
34
votes
2answers
1k views

Does LOGLOG = NLOGLOG?

Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of ...
31
votes
1answer
888 views

Treewidth and the NL vs L Problem

ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in ...
28
votes
2answers
903 views

Tight Lower bounds on Savitch's theorem

First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my ...
26
votes
3answers
770 views

Intermediate problems between L and NL

It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \...
25
votes
4answers
2k views

Separating Logspace from Polynomial time

It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$,...
23
votes
1answer
891 views

Is there any justification to believe that $NL\neq L$?

I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$? It is known that $NL \subset L^2$. The literature on derandomization of $RL$ is pretty convincing that $RL=...
23
votes
1answer
870 views

Logspace algorithms on graphs with bounded tree width

Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor. Courcelle's theorem states that ...
23
votes
2answers
881 views

Best current space lower bound for SAT?

Following on from a previous question, what are the best current space lower bounds for SAT? With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a ...
21
votes
3answers
513 views

space-bounded TMs and oracles

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions). Is such a ...
21
votes
1answer
1k views

Alternate proofs of Immerman-Szelepcsenyi theorem

Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to ...
21
votes
1answer
419 views

Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $. It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (...
20
votes
1answer
880 views

How to prove that USTCONN requires logarithmic space?

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input. Omer Reingold ...
18
votes
4answers
880 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
18
votes
3answers
689 views

CFG parsing using $o(n^2)$ space

There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that. However, all algorithms for ...
18
votes
2answers
644 views

Storage requirements for median selection (two passes algorithms)

In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array. In particular they focus on the following model:...
18
votes
1answer
846 views

Context-sensitive grammar for SAT?

By a classic result of Kuroda, the complexity class NSPACE[$n$] (also known as NLIN-SPACE) is precisely the class CSL of context-sensitive languages. The satisfiability problem SAT is in NSPACE[$n$], ...
17
votes
3answers
2k views

Efficient logspace algorithms

It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, ...
17
votes
1answer
947 views

Quadratic relationship between nondeterministic and deterministic space?

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades. Suppose ...
17
votes
1answer
521 views

Fooling arbitrary symmetric functions

A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
17
votes
1answer
359 views

Which results make quantum space interesting?

Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation? I know many interesting results for quantum computation with sublogarithmic space bounds ...
16
votes
1answer
538 views

Does Nisan's pseudo-random generator relativize?

Nisan proved in "Psuedorandom Generators for Space-Bounded Computation", that there exists a pseudo-random generator which "fools" space-bounded computations. Does this construction hold for every ...
16
votes
1answer
823 views

Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness: Is there a notion of completeness for CSL, and which languages are complete? Are there natural CSL that ...
15
votes
2answers
1k views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
15
votes
2answers
698 views

SC^2 algorithms for st-connectivity

Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is ...
14
votes
2answers
1k views

Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
14
votes
1answer
298 views

Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It ...
13
votes
0answers
346 views

Consequences of bipartite perfect matching not in NL?

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$? I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\...
13
votes
0answers
389 views

Non-deterministic logspace with two-sided error

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 ...
13
votes
0answers
1k views

Is CFL strictly contained in NL?

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$. What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$? Is $\mathsf{CFL}$ a ...
13
votes
0answers
301 views

Is there any known nontrivial result on QIP systems having a space-bounded verifier?

Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier? The only paper I know is An application of quantum finite automata to interactive ...
12
votes
1answer
457 views

Time Hierarchies in DSPACE(O(s(n)))

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}...
12
votes
2answers
351 views

Can multipebble automata decide all deterministic context-sensitive languages?

A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is ...
11
votes
3answers
478 views

How to iterate over vectors in order of probability in small space

Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$. For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. Using these probabilities, is there an efficient ...
11
votes
1answer
291 views

Does the space hierarchy theorem generalize to non-uniform computation?

General Question Does the space hierarchy theorem generalize to non-uniform computation? Here are a few more specific questions: Is $L/poly \subsetneq PSPACE/poly$? For all space ...
11
votes
1answer
546 views

Average-case space complexity

I am trying to find problems whose average-case space complexity has been analyzed. More specifically, I am interested to know if there are any problems with a proven space complexity lower bound ...
11
votes
0answers
2k views

Which algorithm can do a stable in-place binary partition with only O(N) moves?

I'm trying to understand this paper: Stable minimum space partitioning in linear time. It seems that a critical part of the claim is that Algorithm B sorts stably a bit-array of size n in O(nlog2n) ...
10
votes
3answers
1k views

An explicit separation between time-constructibility and space-constructibility?

Show a function $f(n)$ which is space-constructible but not time-constuctible. Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?
10
votes
2answers
338 views

Are non-deterministic tree-walking automata stronger than deterministic ones?

Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton And also this survey: http://www.mimuw.edu.pl/~bojan/...
10
votes
0answers
152 views

Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one? By the usual one I mean the proof based on recursively querying whether there is a midpoint. ...
10
votes
0answers
232 views

Statistical tests between L and LogCFL

Statistical tests are used to check whether a source of randomness is "good". Blum and Goldreich (1992) mentioned two types of statistical tests : (1) deterministic polynomial time statistical tests ...
9
votes
1answer
444 views

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.
9
votes
1answer
164 views

$BPL$ with polylog random bits is in $L$

Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$. My question is ...
9
votes
1answer
203 views

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
8
votes
1answer
295 views

Hamming weight of powers

Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$? If $e\log b$ bits are available, the number can ...
8
votes
1answer
121 views

Can Quarter-Subset Membership be decided space-efficiently?

Consider the following decision problem. Let $q = \sum_{i=0}^{n/4} \binom{n}{i}$ and let $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ be a suitable enumeration of those subsets of $\{0,1,\dots,n-1\}$ that have at ...
8
votes
1answer
299 views

Storing a bit vector in uninitialized memory and minimal space

A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of ...
7
votes
1answer
167 views

Example of an context-sensitive language with a specific number of words of length $n$

Let $s_L(n)$ denote the number of words of length $n$ in $L$. For context-free languages it is known that $s_L(n)$ is either polynomial or exponential. For context-sensitive languages this is probably ...
7
votes
1answer
188 views

Complexity class of efficient streaming algorithms

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words: $L \in \mathsf{StreamL}$ if there ...
7
votes
0answers
251 views

Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...