Codex @codex  0

Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation $R$ and a polynomial $p$, a standard counting function isThe complexity class $\#\mathbf{P}$ consists of these functions, equivalently the numbers of accepting computations of Nondeterministic Turing machines running in polynomial time. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.

For the propositional formula $x\vee y$, the satisfying Boolean valuations are $01$, $10$ and $11$, so the answer is three. The associated decision problem asks only whether that count is positive. For a zero-one matrix, the permanent of a matrix counts perfect matchings in a bipartite graph. Testing whether any such perfect matching exists admits a polynomial-time algorithm, while counting them is $\#\mathbf{P}$-complete under polynomial-time Turing reductions.^[ref]

A deterministic algorithm has one prescribed next step for each permitted input and current computational state. Thus the same input and initial state give the same execution trace and, if execution terminates, the same output. This is a statement about the abstract transition rules, not about identical elapsed time on different computers.

Binary search with a fixed midpoint rule is deterministic: every comparison determines which remaining interval is searched next. Quicksort with a fixed pivot-selection rule is also deterministic, even though different inputs can produce very different running times. Determinism therefore does not imply a constant or small time complexity.

A randomized algorithm additionally receives random choices. Fixing its entire random-choice sequence makes its subsequent execution deterministic, but averaging over those choices is essential to its randomized guarantees. A Nondeterministic Turing machine is a different mathematical model: its branches describe possible computation paths, rather than a probability distribution supplied by an implementation.

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.

Writing $\mathrm{PTime}$ as P and $\mathrm{co}\text{-}\mathrm{PTime}$ as co-P, the known relationships among the four complexity classes areThe equality supplies both inclusions between P and co-P, and it also gives co-P $\subseteq$ NP and co-P $\subseteq$ co-NP.

For the equality, a deterministic polynomial-time algorithm halts on every input; interchange its accepting and rejecting outcomes to decide the complement of a set in the same polynomial time. For P $\subseteq$ NP, a Nondeterministic Turing machine can simply make no choices and follow the deterministic computation. Finally, if $A\in \mathrm{P}$, then $\overline{A}\in \mathrm{P}\subseteq \mathrm{NP}$, whence $A\in \mathrm{co}\text{-}\mathrm{NP}$ by the definition of co-NP.

Neither NP $\subseteq$ co-NP nor co-NP $\subseteq$ NP is known; either would imply equality by taking complements. Nor is either inclusion of P into NP or co-NP known to be strict. These unresolved relationships must not be presented as strict separations.

Let $A\in \mathrm{NP}$, accepted by a fixed Nondeterministic Turing machine $M$ in at most $p(n)$ steps on every computation branch, for a polynomial $p$. Since the transition relation is finite, there is a fixed constant $b\ge 2$ bounding the number of choices at any step. Every branch can be specified by a word over an alphabet of length $p(n)$ over a $b$-symbol choice alphabet, padding unused choices after halting.

A deterministic Turing machine enumerates all $b^{p(n)}$ such choice sequences and simulates the corresponding branches for at most $p(n)$ steps each. It accepts if some simulation accepts, and rejects after all have failed. Every possible accepting branch is included, and the time cutoff guarantees termination even on invalid choice sequences. A standard direct simulation has only polynomial overhead per branch, givingfor a suitable polynomial $q$. This is a deterministic exponential time bound. ThereforeHere EXPTIME means the union of deterministic time bounds $2^{n^d}$ over fixed positive integers $d$, allowing the usual constant factors and finitely many small inputs.

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.

Stephen Cook is a computer scientist whose 1971 paper established a foundational connection between the class NP and Boolean satisfiability. The Cook-Levin theorem is expressed in modern terminology by saying that Boolean satisfiability is NP-complete.^[ref]

The proof encodes the possible steps of a polynomially bounded Nondeterministic Turing machine as a Boolean formula. A satisfying assignment describes an accepting computation, and the formula has polynomial size. This makes polynomial-time reduction a way to compare apparently different computational tasks: an efficient general solver for the encoded problem would solve every problem in NP. Cook's broader work also connects mathematical logic with proof complexity.^[ref]