For faster navigation, this Iframe is preloading the Wikiwand page for NL-complete.

NL-complete

In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine 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 decision problems 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 decision problem 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 is NL-complete) then the language is also NL-complete itself.

Examples

One important NL-complete problem is ST-connectivity (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 with two variables per clause is satisfiable.

The problem of unique decipherability of a given variable-length code was shown to be co-NL-complete by Rytter (1986); Rytter used a variant of the Sardinas–Patterson algorithm 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, Algebra, Linear System, Graph, Finite Automata, Context-free Grammar are listed in Jones (1976).

References

  • Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.
  • Rytter, Wojciech (1986), "The space complexity of the unique decipherability problem", Information Processing Letters, 23 (1): 1–3, doi:10.1016/0020-0190(86)90121-3, MR 0853618.
  • Jones, Neil D.; Lien, Y. Edmund; Laaser, William T (1976). "New problems complete for nondeterministic log space". Mathematical Systems Theory. 10 (1): 1–17. doi:10.1007/BF01683259. S2CID 11530713.
{{bottomLinkPreText}} {{bottomLinkText}}
NL-complete
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?