NL (complexity class)

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

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

properties

According to Immerman and Szelepcsényi's theorem , the NL class is completed under complementation . If co-NL is the class of languages which is the complement of NL , then NL = co-NL.

Relationship to other complexity classes

Since NL is the generalization of class L, every problem in L is also in NL . In addition, the following relationships are known:

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

In the chain above, no inclusion is known to be genuine. The only transitive inclusions that authenticity is known for are:

L ⊂ PSPACE
NL ⊂ PSPACE

This results from the place hierarchy record . For the second line, Savitch's sentence is needed.

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

With the polynomial time algorithm for 2-SAT, it follows that NL is included in P , but it is not known whether NL = P or whether L = NL .

NL-complete problems

The NL class contains complete problems. This means that a problem is not only in NL itself, but that any other problem of class NL can still be reduced to this problem . The calculation of the reduction function also only requires a lot of logarithmic space.

Accessibility problem in graphs

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

2-SAT

Another important NL-complete problem is 2-SAT , a restricted variant of the NP-complete satisfiability problem in propositional logic . However, 2-SAT can be solved in polynomial time. With 2-SAT it is to be decided whether a given propositional formula can be fulfilled, which is available in conjunctive normal form with two literals per clause. One possible problem instance would be

{\ displaystyle (x_ {1} \ vee \ neg x_ {3}) \ wedge (\ neg x_ {2} \ vee x_ ​​{3}) \ wedge (\ neg x_ {1} \ vee \ neg x_ {2} )}

.

The correct answer for this formula is yes, since, for example, a fulfilling assignment of the variable represents. ${\ displaystyle x_ {1} = 1, x_ {2} = 0, x_ {3} = 1}$

Web links

NL . In: Complexity Zoo. (English)