Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}$.) ...
user avatar
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-...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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.) ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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

Complexity status of restricted k-clique

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 $...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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.
user avatar
  • 13

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