About: NP-complete problems

An Entity of Type: Concept, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org:8891

Property	Value
dbo:wikiPageID	1223322 (xsd:integer)
dbo:wikiPageRevisionID	546497342 (xsd:integer)
dbp:wikiPageUsesTemplate	dbt:Cat_main
rdf:type	skos:Concept
rdfs:label	NP-complete problems (en)
skos:broader	dbc:Computational_problems dbc:Computational_complexity_theory
skos:prefLabel	NP-complete problems (en)
skos:related	dbc:NP-hard_problems
prov:wasDerivedFrom	wikipedia-en:Category:NP-complete_problems?oldid=546497342&ns=14
owl:sameAs	dbc:NP-complete_problems
is dbo:wikiPageWikiLink of	dbr:Betweenness dbr:Vehicle_routing_problem dbr:Vertex_cover dbr:Degree-constrained_spanning_tree dbr:Independent_set_(graph_theory) dbr:Induced_subgraph_isomorphism_problem dbr:Instant_Insanity dbr:Light_Up_(puzzle) dbr:Shakashaka dbr:Nurikabe_(puzzle) dbr:Not-all-equal_3-satisfiability dbr:(SAT,_ε-UNSAT) dbr:15_puzzle dbr:Masyu dbr:Maximum_cut dbr:Generalized_assignment_problem dbr:Token_reconfiguration dbr:Quadratic_residue dbr:Radio_coloring dbr:Zero-weight_cycle_problem dbr:Clique_problem dbr:Graph_coloring dbr:Battleship_(puzzle) dbr:Chinese_postman_problem dbr:Steiner_tree_problem dbr:Clique_cover dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Hamiltonian_completion dbr:Hamiltonian_cycle_polynomial dbr:Hamiltonian_path_problem dbr:Traveling_purchaser_problem dbr:Maximum_common_induced_subgraph dbr:Maximum_coverage_problem dbr:Travelling_salesman_problem dbr:Domatic_number dbr:Hashiwokakero dbr:Karp's_21_NP-complete_problems dbr:Minimum_k-cut dbr:Minimum_routing_cost_spanning_tree dbr:3-dimensional_matching dbr:Exact_cover dbr:Graph_partition dbr:Hitori dbr:Hitting_set dbr:Kakuro dbr:Vertex_cycle_cover dbr:List_of_NP-complete_problems dbr:Quadratic_knapsack_problem dbr:Hamiltonian_path dbr:Tetris dbr:Shortest_common_supersequence_problem dbr:Bipartite_dimension dbr:Edge_dominating_set dbr:Dominating_set dbr:Boolean_satisfiability_problem dbr:Planar_SAT dbr:Circuit_satisfiability_problem dbr:Minesweeper_(video_game) dbr:Knapsack_problem dbr:Longest_common_subsequence_problem dbr:Longest_path_problem dbr:Mastermind_(board_game) dbr:SameGame dbr:Satisfiability_modulo_theories dbr:Set_cover_problem dbr:Slitherlink dbr:Unit_disk_graph dbr:Set_TSP_problem dbr:Subgraph_isomorphism_problem dbr:NP-completeness dbr:Monochromatic_triangle dbr:Nonogram dbr:Set_packing dbr:Sudoku dbr:Quadrel dbr:Set_splitting_problem dbr:Tentai_Show
is dcterms:subject of	dbr:Betweenness dbr:Vehicle_routing_problem dbr:Vertex_cover dbr:Degree-constrained_spanning_tree dbr:Independent_set_(graph_theory) dbr:Induced_subgraph_isomorphism_problem dbr:Instant_Insanity dbr:Light_Up_(puzzle) dbr:Shakashaka dbr:Nurikabe_(puzzle) dbr:Not-all-equal_3-satisfiability dbr:(SAT,_ε-UNSAT) dbr:15_puzzle dbr:Masyu dbr:Maximum_cut dbr:Generalized_assignment_problem dbr:Token_reconfiguration dbr:Quadratic_residue dbr:Radio_coloring dbr:Zero-weight_cycle_problem dbr:Clique_problem dbr:Graph_coloring dbr:Battleship_(puzzle) dbr:Chinese_postman_problem dbr:Steiner_tree_problem dbr:Clique_cover dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Hamiltonian_completion dbr:Hamiltonian_cycle_polynomial dbr:Hamiltonian_path_problem dbr:Traveling_purchaser_problem dbr:Maximum_common_induced_subgraph dbr:Maximum_coverage_problem dbr:Travelling_salesman_problem dbr:Domatic_number dbr:Hashiwokakero dbr:Karp's_21_NP-complete_problems dbr:Minimum_k-cut dbr:Minimum_routing_cost_spanning_tree dbr:3-dimensional_matching dbr:Exact_cover dbr:Graph_partition dbr:Hitori dbr:Hitting_set dbr:Kakuro dbr:Vertex_cycle_cover dbr:List_of_NP-complete_problems dbr:Quadratic_knapsack_problem dbr:Hamiltonian_path dbr:Tetris dbr:Shortest_common_supersequence_problem dbr:Bipartite_dimension dbr:Edge_dominating_set dbr:Dominating_set dbr:Boolean_satisfiability_problem dbr:Planar_SAT dbr:Circuit_satisfiability_problem dbr:Minesweeper_(video_game) dbr:Knapsack_problem dbr:Longest_common_subsequence_problem dbr:Longest_path_problem dbr:Mastermind_(board_game) dbr:SameGame dbr:Satisfiability_modulo_theories dbr:Set_cover_problem dbr:Slitherlink dbr:Unit_disk_graph dbr:Set_TSP_problem dbr:Subgraph_isomorphism_problem dbr:NP-completeness dbr:Monochromatic_triangle dbr:Nonogram dbr:Set_packing dbr:Sudoku dbr:Quadrel dbr:Set_splitting_problem dbr:Tentai_Show
is skos:broader of	dbc:Weakly_NP-complete_problems dbc:Minesweeper_(video_game) dbc:Nonograms dbc:SMT_solvers dbc:Number_partitioning dbc:Strongly_NP-complete_problems dbc:Sudoku dbc:Tetris dbc:SAT_solvers
is skos:related of	dbc:NP-hard_problems