complexity class NL
E679191
Complexity class NL is the set of decision problems solvable by a nondeterministic Turing machine using logarithmic space, central to studying space-bounded computation and problems like graph reachability.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| NL | 0 |
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf | complexity class ⓘ |
| acceptanceCondition | existence of an accepting computation path ⓘ |
| alternativeName | NLOGSPACE NERFINISHED ⓘ |
| centralTo | space-bounded computation ⓘ |
| characterizedBy | existence of a path in a configuration graph using O(log n) space ⓘ |
| closedUnder |
Kleene star
NERFINISHED
ⓘ
concatenation ⓘ homomorphism ⓘ inverse homomorphism ⓘ logspace many-one reductions ⓘ union ⓘ |
| complementClass | coNL ⓘ |
| completeProblem |
2-SAT (under logspace reductions)
ⓘ
ST-CONNECTIVITY ⓘ context-free grammar membership (under logspace reductions) ⓘ directed s-t reachability ⓘ graph reachability ⓘ path existence in directed graphs ⓘ |
| configurationGraphSize | polynomial in input size ⓘ |
| contains | L ⓘ |
| definedOver | decision problems ⓘ |
| equalityProofYear | 1987 ⓘ |
| equalityProvedBy |
Neil Immerman
NERFINISHED
ⓘ
Róbert Szelepcsényi NERFINISHED ⓘ |
| fullName | Nondeterministic Logarithmic Space NERFINISHED ⓘ |
| inputAccess | read-only input tape ⓘ |
| inputSizeNotation | n ⓘ |
| logspaceReductionsUsedFor | NL-completeness ⓘ |
| machineModel | nondeterministic Turing machine ⓘ |
| notKnownToBeClosedUnder | complement ⓘ |
| openQuestion |
whether L = NL
ⓘ
whether NL = P ⓘ |
| outputType | decision (yes/no) ⓘ |
| rejectionCondition | no accepting computation path ⓘ |
| relatedResult | NL = coNL ⓘ |
| relatedTo |
L
ⓘ
P ⓘ PSPACE NERFINISHED ⓘ coNL ⓘ |
| resourceBound | logarithmic space ⓘ |
| spaceMeasure | O(log n) work tape cells ⓘ |
| subsetOf |
P
ⓘ
PSPACE NERFINISHED ⓘ |
| supersetOf | L ⓘ |
| typicalMachineRestriction | single work tape with O(log n) cells ⓘ |
| typicalProblemDomain |
graph problems
ⓘ
reachability problems ⓘ verification of simple properties ⓘ |
| usedIn |
complexity theory
ⓘ
theory of computation ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.