patternMinor
What are examples of $\mathsf{NL}$-complete problems?
Viewed 0 times
mathsfwhatareexamplescompleteproblems
Problem
Wikipedia lists exactly two problems as $\mathsf{NL}$-complete - 2-satisfiability and St-connectivity (although stating that there are "several"):
https://en.wikipedia.org/wiki/Category:NL-complete_problems
My old literature on complexity (from study) also has no additional examples. And the complexity zoo also lists the graph reachability problem as sole example:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N
So, are there any other problems known to be $\mathsf{NL}$-complete?
https://en.wikipedia.org/wiki/Category:NL-complete_problems
My old literature on complexity (from study) also has no additional examples. And the complexity zoo also lists the graph reachability problem as sole example:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N
So, are there any other problems known to be $\mathsf{NL}$-complete?
Solution
Here are three more examples, taken from an assignment by Trevisan:
-
Given an NFA and a word, determining whether the NFA accepts the word.
-
Reachability in DAGs.
-
Determining whether a digraph is strongly connected.
Planken shows that the Simple Temporal Problem with bounded weights is NL-complete (see the link for definitions).
There are likely many others. Schaefer's dichotomy theorem, in particular, gives many examples.
-
Given an NFA and a word, determining whether the NFA accepts the word.
-
Reachability in DAGs.
-
Determining whether a digraph is strongly connected.
Planken shows that the Simple Temporal Problem with bounded weights is NL-complete (see the link for definitions).
There are likely many others. Schaefer's dichotomy theorem, in particular, gives many examples.
Context
StackExchange Computer Science Q#57144, answer score: 4
Revisions (0)
No revisions yet.