Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

## Hot answers tagged logspace

19 votes
Accepted

### What are the obstructions to extending $L=SL$ to $L=NL$?

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is ...
16 votes
Accepted

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

Given a satisfiable 2-CNF $\phi$, you can compute a particular satisfying assignment $e$ by an NL-function (that is, there is an NL-predicate $P(\phi,i)$ that tells you whether $e(x_i)$ is true). One ...
• 14.7k
13 votes
Accepted

### What are the consequences of solving XOR 3-SAT in Logspace?

Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your ...
• 1,027
12 votes

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

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
• 5,055
11 votes
Accepted

### On sparse complete sets and P vs L

Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 ...
• 1,733
10 votes

### k-Vertex Cover problem is in parameterized Log space

Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space: Say that a vertex has big degree ...
• 3,216
10 votes
Accepted

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

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.) ...
• 14.7k
9 votes
Accepted

### What are the consequences of $P \subseteq L/poly$?

One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-...
• 1,733
8 votes
Accepted

### It is known that $L \subsetneq PH$?

This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models). And there are oracles making $LOGSPACE = NP$ (the ...
• 26.2k
8 votes

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

This is a favorite question of mine. Fortnow showed, in his paper "Time-Space Tradeoffs for Satisfiability", that $NL$ is properly contained in $\Sigma_{a(n)} P$, where $a(n)$ is any unbounded ...
• 26.2k
6 votes

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

The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction: The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs are still unknown. ...
• 5,424
5 votes
Accepted

### Detecting undirected cycles in logarithmic space

For the undirected cycle problem, you can traverse each connected component: at each node, when coming in through edge $k$, leave through edge $k+1$. (We can assume edges are ordered at each vertex.) ...
• 4,501
4 votes
Accepted

### Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

There is a paper already in 2005 that describes how to do this... See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html I cannot say why people use zig-zag instead, other than ...
• 26.2k
4 votes

### Complexity of comparison unary>binary

The problem is in coNLOGTIME, for example using the following algorithm. As is well known, one can determine the length of input $n$ in binary in DLOGTIME. Then, read off at most $\log n$ bits from ...
• 14.7k
3 votes
Accepted

### Why NL is not L

You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace ...
• 1,704
3 votes
Accepted

### Closure properties of $L$ (DLOGSPACE)?

This question is not research level, even so showing the equivalence of closure under kleene-star to the well known open problem L=NL was a nice challenge. Obviously $S\cap T$ and $S.T$ are in ...
3 votes

Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $... • 801 2 votes ### Why can't Horn-SAT be solved in Log-space? Log-space computations can't modify the input tape. Otherwise you just get linear space. • 14.1k 2 votes ### Complexity of comparison unary>binary It is in uniform AC0 = AltTime(O(1), O(lg n)). Bit(j,i) -- the i-th bit of binary representation of unary number j -- is in uniform AC0. See e.g. Cook and Nguyen, Logical Foundation of Computational ... • 21.3k 2 votes Accepted ### Comparing SAT to MCSP reduction class separations and faster SAT class separations? If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in ... • 26.2k 1 vote ### Why NL is not L People don't know if NL=L or not yet. You showed that NL$\subseteq\$ PSPACE, but it has nothing to do with L.
• 13

Only top scored, non community-wiki answers of a minimum length are eligible