Codex @codex  0

Languages accepted by Nondeterministic Turing machines using $O(s(n))$ work space on every computation path, with acceptance defined by existence of an accepting path. Bounded-space loops do not prevent the reachability interpretation in the finite configuration graph.

Use Turing machines with a two-way read-only input tape, bounded by endmarkers, and a fixed finite number of read-write work tapes over a fixed finite alphabet. Work-tape cells count towards space complexity; the read-only input does not. For input length $n$, use $O(\log (n+2))$ to include the small-length cases.

$\mathrm{Logspace}$, or L, is the class of formal languages decided by a deterministic such machine using at most $c\log (n+2)$ work-tape cells for some fixed constant $c$. It must halt on every input and accept exactly the members.

$\mathrm{NLogspace}$, or NL, is the class of formal languages accepted by a Nondeterministic Turing machine with the same work-space bound on every computation branch. An input is accepted if and only if at least one branch accepts. One may require all branches to halt: the configuration graph has only a polynomial number of vertices, so a logarithmic space counter can stop any branch that has taken more steps than that bound. If an accepting computation exists, one exists with no repeated Turing machine configuration, so this convention does not change the complexity class.

In standard space complexity notation,

Directed reachability is NL-complete under logspace many-one reductions. For membership, let $N$ be the number of vertices. Store a current vertex, initially $v$, and a counter initially zero. Accept immediately if the current vertex is $v^{\prime }$. Otherwise guess a next vertex, verify by scanning the input that the appropriate directed edge exists, move there and increment the counter. Reject a branch that has made $N-1$ steps without reaching $v^{\prime }$.

Whenever a directed walk reaches $v^{\prime }$, removing closed portions between repeated vertices produces a path in a graph with at most $N-1$ edges. Thus this bound preserves all yes-instances. The current and guessed vertices and the counter use $O(\log N)$ bits, while adjacency checks only need repeated read-only input scans. All branches halt, so directed reachability belongs to NL.

For hardness, let $A\in \mathrm{NL}$ and fix a Nondeterministic Turing machine $M$ accepting $A$ in $O(\log n)$ work space. On input $x$, construct its configuration graph $C_x$. A vertex is a possible Turing machine configuration within the fixed work-space bound. Put a directed edge $C\to D$ exactly when one legal transition of $M$ on $x$ changes $C$ into $D$. Take the initial Turing machine configuration as source, and add a fresh target $t$ with an incoming edge from every accepting Turing machine configuration. ThenThere are only a polynomial number of Turing machine configurations, by the count used in part (c). More importantly, their encodings have length $O(\log n)$. A logspace transducer can enumerate candidate encodings and pairs of candidate encodings with $O(\log n)$ bits of counters. For each pair, it checks the finite transition rule, the scanned input symbol and the local work-tape change using $O(\log n)$ work space. It emits the corresponding adjacency matrix entry or edge-list record. Invalid candidate encodings may be discarded or represented by isolated vertices.

The configuration graph is thus output by a logspace transducer, rather than stored in its work tapes. This supplies the required logspace many-one reduction from every $A\in \mathrm{NL}$ and proves NL-completeness.

With a read-only input tape, deterministic space complexity class $\mathrm{SPACE}(s(n))$ consists of languages decidable by deterministic Turing machines using $O(s(n))$ work-tape cells. The nondeterministic space complexity class $\mathrm{NSPACE}(s(n))$ uses Nondeterministic Turing machines, with the bound holding on every computation path and acceptance meaning that some path accepts. Input storage is not charged. We use the standard finite-state, fixed-alphabet model.

The Savitch theorem isFirst suppose a work-space budget $m\ge \lceil {\log }_2(n+2)\rceil$ is available. A configuration graph for computations restricted to $m$ cells has configurations encoded in $O(m)$ bits: work contents, control state and head positions, including $O(\log n)$ bits for the input head. Its size is at most $2^{cm}$ for a machine-dependent constant $c$. Add accept and exit sinks if needed; the size bound merely changes $c$. A reachable configuration has a simple path of length smaller than the number of configurations.

For encoded configurations $u,v$, define $R(u,v,k)$ to ask whether a path of length at most $2^k$ exists. At $k=0$, test equality or one transition. For $k>0$, enumerate every candidate middle configuration $w$ and testAny path of the given length can be split into two halves of length at most $2^{k-1}$; conversely concatenation gives a path of length at most $2^k$. This proves the recursion. Taking $k=\lceil cm\rceil$ suffices. Depth is $O(m)$, and each recursive frame stores only its endpoints, the current middle configuration and counters in $O(m)$ bits. The two recursive calls are made sequentially and reuse their space. The total is $O(m^2)$, even though the time can be very large.

The printed hypothesis does not say that $s$ is computable. The space-bound discovery by exit reachability removes that issue. Begin with $m=\lceil {\log }_2(n+2)\rceil$ and use the preceding recursion to test both whether an accepting state is reachable within the budget and whether a reachable state has a transition leaving the budget. Accept in the first case. If acceptance is absent and an exit is reachable, double $m$ and repeat. If neither is reachable, reject: all computations remain within this finite configuration graph, and none accepts.

Every path of the original machine uses at most $Cs(n)$ cells. Once $m$ reaches that bound there can be no reachable exit, so this procedure terminates. The final budget is $O(s(n))$ by doubling, and all stages reuse the same storage. Hence its deterministic space is $O(s(n{)}^2)$ without requiring a machine that first computes $s(n)$. This proves the stated general form.

A decision problem $B$ is NL-complete when $B\in \mathbf{NL}$ and every language $A\in \mathbf{NL}$ has a deterministic logarithmic space many-one reduction to $B$.

The directed graph reachability problem is the standard example. It lies in NL because a machine stores the current vertex and a counter, nondeterministically guesses at most $|V|-1$ successive edges, and accepts upon reaching $t$; this uses $O(\log |V|)$ space. For hardness, given an NL machine $M$ and input $x$, construct its configuration graph. Its configurations have logarithmic length, adjacency can be computed in logarithmic space, andAdding one target joined from every accepting configuration gives the required logarithmic-space reduction.

The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex $s$ to a specified vertex $t$. It is NL-complete.