Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

4
votes
1answer
161 views

Boolean circuits which correspond to L/poly

Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$. Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
8
votes
1answer
84 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 ...
5
votes
0answers
98 views

Reduction between functions that preserves time and space-complexity

Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed? Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine ...
3
votes
1answer
147 views

Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form: $AB\rightarrow CD$ or $A\rightarrow BC$ or $A\rightarrow B$...
11
votes
1answer
189 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 ...
3
votes
0answers
30 views

references for optimal computation under memory constraint?

Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width) There is this reference ...
2
votes
0answers
93 views

Is scalable hardware support for LogCFL (= sAC^1) possible?

The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, ...
3
votes
1answer
218 views

NFA to 2DFA: what are the upper and lower bounds?

Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
12
votes
1answer
325 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}...
17
votes
1answer
894 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 ...
5
votes
1answer
109 views

Base extension in residue number systems with low space

Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes ...
1
vote
0answers
50 views

Circuit games in extensive form with imperfect information

Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with ...
4
votes
0answers
119 views

Is there a certificate definition for polyL?

Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?
3
votes
6answers
365 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
2
votes
1answer
347 views

Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Let $M$ be a probabilistic Turing machine with a unary input $n$ whose space is bounded by a polynomial in $n$ and its output is a distribution $D$ over binary strings. Note that the number of ...
13
votes
0answers
224 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 $\...
9
votes
1answer
108 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 ...
10
votes
1answer
156 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 ...
4
votes
0answers
155 views

Is anything known about Sokoban with only 1 box?

This is intended to be a simpler version of my earlier question here. In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is the corresponding decision problem, and 1-Sokoban ...
7
votes
0answers
166 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-...
19
votes
1answer
530 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 ...
0
votes
1answer
73 views

An algorithm for counting to Graham’s Number

I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory. I thougth of the way to organize counter suitable for ...
6
votes
0answers
148 views

What is the space complexity of computing the eigenvectors of a matrix?

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
7
votes
0answers
373 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$-...
1
vote
0answers
73 views

What is the minimal known space for polytime algorithms

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds?...
5
votes
1answer
686 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
22
votes
2answers
699 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 ...
4
votes
1answer
179 views

Satisfiability for various branching programs

Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community. Branching program, or BDD is one of the most basic and popular ...
3
votes
1answer
157 views

Number of bits required for encoding variables with fixed sum?

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$ It's easy to store the variables using $r\...
4
votes
2answers
166 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 ...
12
votes
3answers
444 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 ...
4
votes
1answer
194 views

Low space computation and branching program

One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$. I ...
21
votes
1answer
375 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) (...
12
votes
0answers
333 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 ...
8
votes
1answer
260 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 ...
6
votes
1answer
157 views

How big is NSC^k?

It is well known that $\mathsf{NL} \subseteq \mathsf{NC} \subseteq \mathsf{P}$, both inclusions conjectured to be proper. On the other hand $\mathsf{NP} \supseteq \mathsf{P}$, also probably a proper ...
11
votes
0answers
685 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 ...
1
vote
1answer
222 views

Super-logspace mapping reducibility

There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to ...
11
votes
2answers
308 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 ...
17
votes
1answer
323 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 ...
13
votes
0answers
299 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 ...
3
votes
0answers
219 views

$NC^i \subseteq DSPACE[\log^i{n}]$?

The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by: start with an $O(\log{n})$-depth polynomial sized ...
31
votes
1answer
834 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 ...
6
votes
0answers
447 views

Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? [closed]

We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the ...
16
votes
1answer
669 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
624 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 ...
8
votes
1answer
256 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 ...
2
votes
1answer
228 views

Simulating nondeterministic space-bounded computation using randomness

Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer ...
9
votes
2answers
282 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/...
8
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(...