NPCompletenessProvedBy
P142028
predicate
Indicates that the NP-completeness of a problem is established through a proof provided by a particular person, work, or method.
Observed surface forms (3)
| Surface form | Occurrences |
|---|---|
| establishesNPCompletenessOf | 19 |
| npCompletenessProofBy | 2 |
| npCompletenessProofPublication | 1 |
Sample triples (23)
| Subject | Object |
|---|---|
| SAT problem | Stephen Cook NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Satisfiability problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Clique problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Vertex Cover problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Hamiltonian Cycle problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Traveling Salesman problem (decision version) via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Set Covering problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Feedback Vertex Set problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Chromatic Number problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Partition problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Knapsack problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Exact Cover problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Hitting Set problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Steiner Tree problem (decision version) via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Job Sequencing problem (NP-complete variant) via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
3-Dimensional Matching problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Subset Sum problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Set Packing problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Node Cover problem via predicate surface "establishesNPCompletenessOf" ⓘ |
|
"Reducibility Among Combinatorial Problems" (1972)
surface form:
Reducibility Among Combinatorial Problems
|
Exact Cover by 3-Sets problem via predicate surface "establishesNPCompletenessOf" NERFINISHED ⓘ |
| SAT | Stephen Cook via predicate surface "npCompletenessProofBy" NERFINISHED ⓘ |
| SAT | Leonid Levin via predicate surface "npCompletenessProofBy" NERFINISHED ⓘ |
| SAT | The Complexity of Theorem-Proving Procedures via predicate surface "npCompletenessProofPublication" NERFINISHED ⓘ |