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 ...
- 306
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,067
13
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,675
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,763
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,276
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,763
9
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 ...
- 2,356
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 ...
- 27.7k
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, ...
- 2,356
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. ...
- 6,795
4
votes
Accepted
Logspace computation of Zeckendorf representation
Conversion from binary to the Zeckendorf representation can be done in uniform $\def\tc{\mathrm{TC}^0}\tc$, and a fortiori in logspace.
To fix notation, the Zeckendorf representation of a natural ...
- 18.6k
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 ...
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 ...
- 18.6k
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 ...
- 2,194
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 ...
- 27.7k
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 $...
- 851
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 ...
- 851
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 ...
- 27.7k
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.
- 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 ...
- 21.8k
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 ...
- 19
Only top scored, non community-wiki answers of a minimum length are eligible