# Questions tagged [logspace]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
97 views

• 12.6k
118 views

$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it. Following inclusions are known: $$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\... • 12.6k 1 vote 0 answers 64 views ### Reference to "compressibility" of logarithmic space [closed] Is there a reference somewhere for the result SPACE(O(\log n)) = SPACE(\log n)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ... 10 votes 0 answers 160 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. ... • 1,439 1 vote 2 answers 1k views ### Why NL is not L I'm a beginner in learning complexity and get confused at NL. NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words, NL = NSPACE(\... 3 votes 0 answers 126 views ### Is Circuit Minimization P-hard under logspace reductions? By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string x and a number k. Question: Does there exist a Boolean Circuit C... • 5,005 3 votes 0 answers 235 views ### What is consequence of PH\subseteq NSPACE((\log n)^2)? What is consequences of PH\subseteq NSPACE((\log n)^2)? We don't even know PH is equals to L or not. I am wondering what will be happened when PH\subseteq NSPACE((\log n)^2)? 6 votes 1 answer 576 views ### What are the consequences of solving XOR 3-SAT in Logspace? XOR Formulas Consider boolean formulas with connectives \wedge (AND) and \oplus (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of \oplus-clauses. An \... • 5,005 2 votes 0 answers 414 views ### Is there any NC-complete problem with respect to logspace reduction? The question is on the title. We all know that \text{NL} and \text{P} have such problems. So I wonder the same thing about \text{NC}. More interestingly, is there any k \ge 2 and any \text{... 9 votes 1 answer 201 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 ... • 383 4 votes 1 answer 227 views ### Can L=SL be shown with the replacement product instead of the zig-zag product? (This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.) In Omer Reingold's logspace USTCON ... • 757 13 votes 1 answer 495 views ### What are the obstructions to extending L=SL to L=NL? Omer Reingold's proof that L=SL gives an algorithm for USTCON (In an Undirected graph with special vertices s and t, are they Connected?) using only logspace. The basic idea is to build an ... • 757 10 votes 1 answer 220 views ### On sparse complete sets and P vs L Mahaney's Theorem tells us that if there is a sparse NP-complete set under polynomial-time many-one reductions, then P = NP. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ... • 5,005 14 votes 1 answer 340 views ### What are the consequences of P \subseteq L/poly? A language is in L/poly if there exists a logspace Turing machine that decides the language with polynomial amount of advice. See here for more info: https://en.wikipedia.org/wiki/L/poly ... • 5,005 9 votes 0 answers 711 views ### Is it known if \mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))? \mathrm{CFL} is the class of context-free languages. Question Is \mathrm{CFL} known to be solvable in o(log^{2}(n)) non-deterministic space? What about \mathrm{DCFL}? • 5,005 3 votes 1 answer 445 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? • 496 -2 votes 1 answer 275 views ### Closure properties of L (DLOGSPACE)? [closed] What are the closure properties of L (DLOGSPACE)? I'm not only intrested in these properties (if of course S and T are in L) : S \cap T S^* (kleene-star) S.T (concat) • 151 0 votes 1 answer 101 views ### Complexity status of restricted k-clique [closed] Restricted k-clique: Input: (G,v,k) where v is vertex in V Output: k-clique containing vertex v. What is the space and time complexity status of this Restricted k-clique problem? Is ... • 175 3 votes 0 answers 116 views ### Restricted k-set cover is in NL or L Restricted k-set cover: Input: (U,S_1,S_2,\cdots, S_n, k), U=[n] and S_i\subseteq U for all 1\leq i \leq n. Output: \bigcap_{i\in I}S_i where I=\{1,i_1,i_2\cdots,i_k\}, i_1=min(S_1),i_2=... • 175 6 votes 2 answers 548 views ### Complexity of comparison unary>binary What is the smallest widely-known complexity class to which$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\... 207 views

### On space complexity of permanent modulo $2^t$?

We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current ...
• 12.6k
1 vote
70 views

• 175
113 views

### Number theoretic problems complete for $\mathsf{RL}$

Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$? Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete ... 96 views

### Are there any non-relativized separations between $L$ and $PH$?

In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
• 757
751 views

### What is the power of general poly-size permutation branching programs?

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
• 4,973
228 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 ...
• 161
966 views

### Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$. Are there any known connections between the problems: P vs L, UP vs UL, NP ...
• 5,005
468 views

### Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$

If $\mathsf{L = NL}$, then there is a logspace algorithm that solves the decision version of 2-SAT. Is $\mathsf{L = NL}$ known to imply that there is a logspace algorithm to obtain a satisfying ... 259 views

### Why can't Horn-SAT be solved in Log-space? [closed]

A simple algorithm for Horn-SAT (in CNF) is the following: Given: A Horn formula $\phi$ in CNF. Find a unit clause (a clause with one literal) $C_i$. $~$Set the variable $x_j$ appearing in $C_i$ to ...
243 views

### Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
• 13.8k
495 views

### What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the Karp-...
• 4,973
283 views

### Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
2k views

### Detecting undirected cycles in logarithmic space [closed]

I have a lot of difficulties with constructing algorithms that use $O(\log n)$ space, as I am unsure about how much can be stored on the worktape. I am trying to figure out an algorithm for the ...
• 131