# Tag Info

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

12

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

The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See M. Grohe, Equivalence in finite-variable logics is complete for polynomial time. Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.) Note that colour refinement equivalence corresponds to ...

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

10

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

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

5

A two-way deterministic (nondeterministic) multi-head finite automaton can be simulated by a logspace DTM (NTM), and vice versa. So, for including class $\mathsf{NL}$, you do not need a counter! The value of the counter belonging to a two-way nondeterministic multi-head finite automaton with one-counter can be bounded by a polynomial, otherwise, the ...

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

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

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

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