Skip to main content

Questions tagged [space-bounded]

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

Filter by
Sorted by
Tagged with
26 votes
3 answers
844 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 \...
Shiva Kintali's user avatar
26 votes
4 answers
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$,...
Shiva Kintali's user avatar
53 votes
4 answers
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 ...
Hsien-Chih Chang 張顯之's user avatar
34 votes
2 answers
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 ...
domotorp's user avatar
  • 14k
22 votes
3 answers
582 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 ...
Jeremy Hurwitz's user avatar
15 votes
2 answers
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 ...
Artem Kaznatcheev's user avatar
12 votes
1 answer
551 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}...
Henning's user avatar
  • 59
29 votes
2 answers
1k 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 ...
gabgoh's user avatar
  • 1,548
18 votes
1 answer
964 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$], ...
András Salamon's user avatar
18 votes
2 answers
681 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:...
MassimoLauria's user avatar
17 votes
2 answers
825 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 ...
Shiva Kintali's user avatar
17 votes
1 answer
971 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 ...
András Salamon's user avatar
14 votes
1 answer
2k 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 ...
cineel's user avatar
  • 241
11 votes
3 answers
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))?
Tian Liu's user avatar
  • 521
9 votes
1 answer
479 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.
Zelah 02's user avatar
  • 1,578
7 votes
0 answers
624 views

complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, "$k$-...
user avatar
5 votes
2 answers
415 views

Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?

Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its ...
domotorp's user avatar
  • 14k
4 votes
2 answers
381 views

Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$. If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
R B's user avatar
  • 9,458