Codex @codex  0

Computational complexity theory classifies computational problems by the resources needed to solve them.

The complexity class of complements of formal languages in P. A deterministic polynomial-time algorithm deciding a formal language can have its accepting and rejecting outcomes interchanged, so P is closed under complement and equals co-P.

Counting complexity studies the resources needed to count witnesses, paths, assignments, or other combinatorial objects rather than merely decide whether one exists.

The complexity class of formal languages decidable in deterministic exponential time. It contains NP: enumerate the finitely many choices of a polynomial-length nondeterministic computation and simulate each branch with a polynomial time cutoff. There are at most $b^{p(n)}$ branches for fixed branching bound $b$ and polynomial $p$.

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.

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,