A decision problem is NL-complete when it belongs to NL and every problem in NL reduces to it by a deterministic logarithmic-space many-one reduction.
The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex to a specified vertex . It is NL-complete.
The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.

Ancestors (8)

  1. NL (complexity)
  2. Logarithmic space
  3. Space complexity
  4. Complexity class
  5. Computational complexity theory
  6. Theoretical computer science
  7. Computer science
  8. Home

Synonyms (1)

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version