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 ...
Scott Aaronson's 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 ...
Gustav Nordh's user avatar
  • 1,047
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 ...
Or Meir's user avatar
  • 5,370
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 ...
William Hoza's 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 ...
daniello's user avatar
  • 3,266
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-...
William Hoza's user avatar
  • 1,733
8 votes
Accepted

Is Circuit Minimization $P$-hard under logspace reductions?

The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
Eric Allender's user avatar
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 ...
Ryan Williams's user avatar
7 votes
Accepted

What circuit depth is enough to compute a log-space complete problem?

It seems that nobody has added to the discussion of this question since February. I'm quite sure that no better depth upper bound is known for L than $\log^2 n$, in the bounded fan-in circuit model, ...
Eric Allender's 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. ...
Hermann Gruber's user avatar
4 votes

A super-linear time problem in NL

I believe that the "state of the art" is that it is extremely hard to prove superlinear lower bounds even for NP-complete problems. If you're fine with conditional lower bounds, then the ...
Lê Thành Dũng Nguyễn's 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 ...
Emil Jeřábek's user avatar
4 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 ...
Lieuwe Vinkhuijzen's 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 ...
Ryan Williams's 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 $...
TheoryQuest1's user avatar
3 votes

Can Lexicographic BFS be implemented in logspace?

It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) $u_1$ be $v_1$, and the next elements $u_2$, $u_3$, etc., of the output, be the neighbors of $v_1$ according to the input ...
Siddharth's user avatar
  • 823
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 ...
Ryan Williams's user avatar
2 votes

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.
Snjór's user avatar
  • 23
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 ...
Kaveh's user avatar
  • 21.6k
1 vote

Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

It is not known whether CFL is contained in space o(log^2(n)). If CFL were contained in space o(log^2(n)), then NL would also be contained in space o(log^2(n)). The question whether NL is contained in ...
user69092's user avatar

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