8 votes

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

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
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
  • 833
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