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).
All labels observed (3)
| Label | Occurrences |
|---|---|
| statusIfPEqualsNP | 2 |
| isNPCompleteBecause | 1 |
| relationToNPCompleteness canonical | 1 |
Description generation (PDg)
The one-sentence description above was generated by prompting gpt-5.1 with the predicate name and this instruction.
Instruction
Given a predicate that represents a relationship or action between entities, generate a one-sentence description explaining its meaning. # Instructions Focus on describing the relationship, not the entities themselves. # Response Format Begin the description with \' Indicates...\'
Input
Predicate: relationToNPCompleteness
Generated description
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).
Sample triples (4)
| Subject | Object |
|---|---|
|
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" ⓘ |
| 3-SAT | would be solvable in polynomial time via predicate surface "statusIfPEqualsNP" ⓘ |
| Clique problem | would be solvable in polynomial time via predicate surface "statusIfPEqualsNP" ⓘ |