GPTKB
Browse
Query
Compare
Download
Publications
Contributors
Search
Karp's 21 NP-complete problems
URI:
https://gptkb.org/entity/Karp's_21_NP-complete_problems
GPTKB entity
Statements (41)
Predicate
Object
gptkbp:instanceOf
list of computational problems
gptkbp:allProblemsAre
NP-complete
gptkbp:author
gptkb:Richard_M._Karp
gptkbp:basisFor
further research in NP-completeness
gptkbp:field
computer science
theoretical computer science
https://www.w3.org/2000/01/rdf-schema#label
Karp's 21 NP-complete problems
gptkbp:includes
gptkb:0-1_Integer_Programming
gptkb:3-Dimensional_Matching
gptkb:3-SAT
gptkb:Chromatic_Number
gptkb:Clique_Cover
gptkb:Exact_Cover
gptkb:Exact_Set_Cover
gptkb:Feedback_Arc_Set
gptkb:Hamiltonian_Cycle
gptkb:Hamiltonian_Path
gptkb:Hitting_Set
gptkb:Knapsack_Problem
gptkb:Max_Cut
gptkb:Partition_Problem
gptkb:Satisfiability_(SAT)
gptkb:Set_Covering
gptkb:Steiner_Tree
gptkb:Subset_Sum
gptkb:Traveling_Salesman_Problem_(decision_version)
gptkb:Vertex_Cover
gptkb:Clique
Feedback Node Set
Minimum Cover
Set Packing
gptkbp:influenced
theoretical computer science
algorithm design
gptkbp:numberOfRooms
21
gptkbp:publicationYear
1972
gptkbp:publishedIn
A paper titled 'Reducibility Among Combinatorial Problems'
gptkbp:significance
First systematic list of NP-complete problems
gptkbp:bfsParent
gptkb:Richard_Karp
gptkb:NP-completeness
gptkb:P_vs_NP_problem
gptkbp:bfsLayer
5