# Tag Info

## Hot answers tagged logspace

19

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 a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex,...

16

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 way to do that is described below. I will freely use the fact that NL is closed under $\mathrm{AC}^0$-reductions, hence NL-functions are closed under ...

13

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 questions: (1) Open (2) $\oplus L = L$ (3) Yes

12

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 decreased to $O(S)$. In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can ...

11

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 and proven by Cai and Sivakumar in 1995. See this paper. Hartmanis also conjectured that if there is a sparse $\mathbf{NL}$-complete set under log-space many-...

10

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 if it has degree at least $k+1$. All vertices of big degree must be in every vertex cover of size at most $k$. If $v$ does not have big degree it has small ...

10

$\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}$.) The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a ...

9

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-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence ...

8

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 PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).

8

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 function. That is, nondeterministic logspace is properly contained in alternating polynomial time with $a(n)$ alternations. Showing that $NL$ is not in $\Sigma_k P$ ...

6

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. The problem of stating them was raised in 1978 by Sakoda and Sipser , with the conjecture that they are not polynomial. In spite of all attempts to ...

5

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.) Now vou start such a traversal once from every node $v$, remembering only $v$ and the edge you left $v$ through. If the traversal returns to $v$ through a ...

4

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 perhaps they found the original reference readable enough that they did not need to look at secondary literature. At least for teaching purposes it seems the ...

4

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 the end of the input to find $j$ (if it is longer, reject). This also determines $i=n-1-\lfloor\log(j+1)\rfloor$ (I am assuming one character for the separator), ...

3

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 machine could enumerate all these states, and check whether one of them is accepting. But this is not enough. To faithfully simulate the NL machine, the ...

3

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 DLOGSPACE, if $S$ and $T$ are in DLOGSPACE. For $S\cap T$, you run both the machine for $S$ and for $T$, and accept if and only if both accepted. For $S^*$, see ...

3

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 $v$. $v$ is connected to all vertices in the graph. The problem is still NPComplete.

2

Log-space computations can't modify the input tape. Otherwise you just get linear space.

2

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 Complexity, 2010. Comparison then is just two log bounded quantifiers.

2

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 this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot ...

1

People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.

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