relationToNPCompleteness
P142791
predicate
Indicates that the subject has a defined conceptual or formal connection to the notion of NP-completeness (e.g., being NP-complete, related to NP-complete problems, or used in reasoning about NP-completeness).
Observed surface forms (2)
- statusIfPEqualsNP ×2
- isNPCompleteBecause ×1
Sample triples (4)
| Subject | Object |
|---|---|
| 3-SAT | would be solvable in polynomial time via predicate surface "statusIfPEqualsNP" ⓘ |
| Clique problem | would be solvable in polynomial time via predicate surface "statusIfPEqualsNP" ⓘ |
|
Karp reductions
surface form:
Karp reduction
|
used to define NP-complete problems ⓘ |
| SAT | every problem in NP can be reduced to SAT in polynomial time via predicate surface "isNPCompleteBecause" ⓘ |