# Tagged Questions

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

80 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 ...
312 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 ...
68 views

124 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 ...
438 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 ...
157 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 ...
342 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) (...
303 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 ...
235 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 ...
133 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 ...
457 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 ...
206 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 ...
293 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 ...
309 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 ...
290 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 ...
206 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 ...
787 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 ...
418 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 ...
560 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$], ...
584 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 ...
225 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 ...
223 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 ...
261 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/...
1k 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(...
420 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 ...
773 views

271 views

### compressing rarely used space

So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space. But let's say that it ...
716 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 ...
388 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.