|
gptkbp:instanceOf
|
computational complexity class
|
|
gptkbp:characterizedBy
|
at least as hard as the hardest problems in NP
|
|
gptkbp:definedIn
|
theoretical computer science
|
|
gptkbp:firstDefined
|
gptkb:Richard_Karp
gptkb:Stephen_Cook
1970s
|
|
gptkbp:hasProperty
|
no known polynomial-time solution
optimization or decision problems
solution can be verified in polynomial time (if in NP)
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
NP-hard problems
|
|
gptkbp:includes
|
gptkb:bin_packing_problem
gptkb:3-partition_problem
gptkb:Hamiltonian_cycle_problem_(optimization_version)
gptkb:boolean_satisfiability_problem_(optimization_version)
gptkb:clique_problem_(optimization_version)
gptkb:crossword_puzzle_(generalized_version)
gptkb:graph_coloring_(optimization_version)
gptkb:k-SAT_(for_k_≥_3,_optimization_version)
gptkb:knapsack_problem_(optimization_version)
gptkb:maximum_independent_set_(optimization_version)
gptkb:set_cover_problem_(optimization_version)
gptkb:set_splitting_problem
gptkb:subset_sum_problem_(optimization_version)
gptkb:sudoku_(generalized_version)
gptkb:traveling_salesman_problem_(optimization_version)
gptkb:vertex_cover_problem_(optimization_version)
halting problem
NP-complete problems
integer programming
subset sum problem
partition problem
job shop scheduling
maximum cut (optimization version)
minimum dominating set
minimum makespan scheduling
graph isomorphism (not known to be NP-hard or in P)
|
|
gptkbp:mayNotBe
|
in NP
|
|
gptkbp:notSolvableBy
|
polynomial-time algorithms (unless P=NP)
|
|
gptkbp:reductionType
|
polynomial-time reduction
|
|
gptkbp:relatedTo
|
gptkb:P_vs_NP_problem
NP-complete problems
EXPTIME-hard problems
PSPACE-hard problems
co-NP-hard problems
|
|
gptkbp:solvedBy
|
heuristics
brute-force algorithms
approximation algorithms (for some problems)
|
|
gptkbp:studiedIn
|
gptkb:mathematics
operations research
theoretical computer science
|
|
gptkbp:bfsParent
|
gptkb:Quantum_Approximate_Optimization_Algorithm
gptkb:NP_(complexity_class)
gptkb:NP_(nondeterministic_polynomial_time)
gptkb:Approximation_Algorithms_for_NP-hard_Problems
|
|
gptkbp:bfsLayer
|
6
|