NPCompletenessProvedBy

P142028

predicate

Indicates that the NP-completeness of a problem is established through a proof provided by a particular person, work, or method.

Try in SPARQL

All labels observed (4)

Label	Occurrences
establishesNPCompletenessOf	19
npCompletenessProofBy	2
NPCompletenessProvedBy canonical	1
npCompletenessProofPublication	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: NPCompletenessProvedBy

Generated description

Indicates that the NP-completeness of a problem is established through a proof provided by a particular person, work, or method.

Sample triples (23)

Subject	Object
SAT problem	Stephen Cook ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Satisfiability problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Clique problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Vertex Cover problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Hamiltonian Cycle problem via predicate surface "establishesNPCompletenessOf" ⓘ linked to: Hamiltonian cycle concept
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Traveling Salesman problem (decision version) via predicate surface "establishesNPCompletenessOf" ⓘ linked to: traveling salesman problem
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Set Covering problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Feedback Vertex Set problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Chromatic Number problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Partition problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Knapsack problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Exact Cover problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Hitting Set problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Steiner Tree problem (decision version) via predicate surface "establishesNPCompletenessOf" ⓘ linked to: Steiner tree problem
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Job Sequencing problem (NP-complete variant) via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	3-Dimensional Matching problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Subset Sum problem via predicate surface "establishesNPCompletenessOf" ⓘ linked to: Subset sum problem
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Set Packing problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Node Cover problem via predicate surface "establishesNPCompletenessOf" ⓘ
Reducibility Among Combinatorial Problems linked to: "Reducibility Among Combinatorial Problems" (1972)	Exact Cover by 3-Sets problem via predicate surface "establishesNPCompletenessOf" ⓘ linked to: Exact Cover problem
SAT	Stephen Cook via predicate surface "npCompletenessProofBy" ⓘ
SAT	Leonid Levin via predicate surface "npCompletenessProofBy" ⓘ
SAT	The Complexity of Theorem-Proving Procedures via predicate surface "npCompletenessProofPublication" ⓘ linked to: "The Complexity of Theorem-Proving Procedures"