computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, NL-complete is a

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

containing the languages that are

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

for NL, the class of

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

s that can be solved by a

nondeterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

using a logarithmic amount of memory space. The NL-complete languages are the most "difficult" or "expressive" problems in NL. If a deterministic algorithm exists for solving any one of the NL-complete problems in logarithmic memory space, then NL = L.

Definitions

NL consists of the

s that can be solved by a nondeterministic Turing machine with a read-only input tape and a separate read-write tape whose size is limited to be proportional to the logarithm of the input length. Similarly, L consists of the languages that can be solved by a deterministic Turing machine with the same assumptions about tape length. Because there are only a polynomial number of distinct configurations of these machines, both L and NL are subsets of the class P of deterministic polynomial-time decision problems. Formally, a

is NL-complete when it belongs to NL, and has the additional property that every other decision problem in NL can be reduced to it. Unless otherwise specified, the reductions in this definition are assumed to be many-one reductions by a deterministic logarithmic-space algorithm.

Properties

If an NL-complete language ''X'' could belong to L, then so would every other language ''Y'' in NL. For, suppose (by NL-completeness) that there existed a deterministic logspace reduction ''r'' that maps an instance ''y'' of problem ''Y'' to an instance ''x'' of problem ''X'', and also (by the assumption that ''X'' is in L) that there exists a deterministic logspace algorithm ''A'' for solving problem ''X''. With these assumptions, a problem ''y'' in language Y could be solved in logarithmic space by an algorithm that simulates the behavior of algorithm ''A'' on input ''r''(''y''), using the reduction algorithm to simulate each access to the read-only tape for ''r''(''y''). It follows from the Immerman–Szelepcsényi theorem that, if a language is co-NL-complete (that is, if its

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

is NL-complete) then the language is also NL-complete itself.

Examples

One important NL-complete problem is

ST-connectivity In computer science, st-connectivity or STCON is a decision problem asking, for vertices ''s'' and ''t'' in a directed graph, if ''t'' is reachable from ''s''. Formally, the decision problem is given by :. Complexity On a sequential computer ...

(or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph ''G'' and two nodes ''s'' and ''t'' on that graph, there is a path from ''s'' to ''t''. ST-connectivity can be seen to be in NL, because we start at the node ''s'' and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state. Another important NL-complete problem is 2-satisfiability (Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in

conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...

with two variables per clause is satisfiable. The problem of unique decipherability of a given

variable-length code In coding theory a variable-length code is a code which maps source symbols to a ''variable'' number of bits. Variable-length codes can allow sources to be compressed and decompressed with ''zero'' error (lossless data compression) and still be ...

was shown to be co-NL-complete by ; Rytter used a variant of the

Sardinas–Patterson algorithm In coding theory, the Sardinas–Patterson algorithm is a classical algorithm for determining in polynomial time whether a given variable-length code is uniquely decodable, named after August Albert Sardinas and George W. Patterson, who published i ...

to show that the complementary problem, finding a string that has multiple ambiguous decodings, belongs to NL. Because of the Immerman–Szelepcsényi theorem, it follows that unique decipherability is also NL-complete. Additional NL-complete problems on

Propositional Logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...

, Algebra, Linear System, Graph,

Finite Automata A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

Context-free Grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empt ...

are listed in Jones (1976).

References

* *. *{{cite journal , author-link=Neil D. Jones , last1=Jones , first1=Neil D. , last2=Lien , first2=Y. Edmund , last3=Laaser , first3=William T , date=1976 , title=New problems complete for nondeterministic log space , journal=Mathematical Systems Theory , volume=10 , issue=1 , pages=1–17 , doi=10.1007/BF01683259, s2cid=11530713 Complexity classes