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

# Tag Info

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 ...
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 ...
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 ...

### $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 ...
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 ...

### 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 ...
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}$.) ...
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-...
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 ...

### 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 ...

### 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. ...
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.) ...
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 ...

### 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 ...
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 ...
### 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 ...