NL (complexity)

In complexity theory NL denotes the class of decision problems that can be solved by a nondeterministic Turing machine in logarithmic space.

NL is an extension of the class L, which is defined analogously for deterministic Turing machines.

Properties

By the theorem of Immerman and Szelepcsényi the class NL is closed under complement. If co - NL is the class of languages ​​which forms the complement of NL, then applies NL = co -NL.

Relation to other complexity classes

Since NL is the generalization of the class L, every problem is in L and in NL. Additionally, the following relationships are known:

In the above chain is known for no inclusion, whether it is genuine. The only transitive inclusions, for which the authenticity is known are:

  • L ⊂ PSPACE
  • NL ⊂ PSPACE

This results from the space hierarchy theorem. The set of Savitch still needed for the second row.

It is known, however, that the equality NL = RL applies. The class RL is defined analogously to NL for probabilistic Turing machines.

Since we have a polynomial time algorithm for 2- SAT, we know that NL is contained in P, but it is not known whether NL = P or if L = NL.

NL- complete problems

The class NL contains complete problems. This means that not only is a problem even in NL, but that continue to be reduced every other problem of class NL on this problem. The calculation of the reduction function is also needed while only logarithmic amount of space.

Reachability problem in graphs

The decision problem whether in a directed graph is a path between two given nodes exist ( STCON ) is NL -complete.

2- SAT

Another important NL -complete problem is 2- SAT, a restricted variant of the NP-complete satisfiability problem of propositional logic. 2- SAT is solvable in polynomial time, however. On 2- SAT is to be decided whether a given propositional formula can be satisfied, which is in conjunctive normal form with two literals per clause. A possible problem instance would be

The correct answer for this formula is "yes ", as for example, a satisfying assignment of the variables represents.

Recursive set Non-deterministic Turing machine Savitch's theorem Time complexity#Polynomial time Propositional calculus
606406
de