decisionProblem
P132452
predicate
Indicates that the subject is a computational problem for which the task is to decide, with a yes/no answer, whether given inputs satisfy a specified condition.
Observed surface forms (5)
- hasDecisionProblem ×3
- decisionProblemType ×2
- decisionQuestion ×2
- concernsDecisionProblems ×1
- decisionProblemComplexity ×1
Sample triples (10)
| Subject | Object |
|---|---|
| 3-SAT | is the given 3-CNF formula satisfiable via predicate surface "decisionQuestion" ⓘ |
|
complexity class BPP
surface form:
BPP
|
language recognition via predicate surface "decisionProblemType" ⓘ |
| Cook–Levin theorem | yes via predicate surface "concernsDecisionProblems" ⓘ |
| Eulerian digraph | linear time in number of vertices plus edges via predicate surface "decisionProblemComplexity" ⓘ |
| Eulerian digraph | testing whether a given digraph is Eulerian via predicate surface "hasDecisionProblem" ⓘ |
|
Hamiltonian cycle concept
surface form:
Hamiltonian cycle
|
Hamiltonian cycle problem ⓘ |
| LTL | model checking via predicate surface "hasDecisionProblem" ⓘ |
| LTL | satisfiability via predicate surface "hasDecisionProblem" ⓘ |
| Post correspondence problem | existence of a matching sequence of indices via predicate surface "decisionQuestion" ⓘ |
|
complexity class RP
surface form:
RP
|
languages over finite alphabets via predicate surface "decisionProblemType" ⓘ |