Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Karps_21_NP-complete_problems> ?p ?o }
Showing triples 1 to 81 of
81
with 100 triples per page.
- Karps_21_NP-complete_problems abstract "In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, \"Reducibility Among Combinatorial Problems\", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem.".
- Karps_21_NP-complete_problems wikiPageExternalLink karp.pdf.
- Karps_21_NP-complete_problems wikiPageExternalLink 192662.html.
- Karps_21_NP-complete_problems wikiPageExternalLink citation.cfm?coll=GUIDE&dl=GUIDE&id=805047.
- Karps_21_NP-complete_problems wikiPageID "2012564".
- Karps_21_NP-complete_problems wikiPageLength "4566".
- Karps_21_NP-complete_problems wikiPageOutDegree "49".
- Karps_21_NP-complete_problems wikiPageRevisionID "698180492".
- Karps_21_NP-complete_problems wikiPageWikiLink 3-dimensional_matching.
- Karps_21_NP-complete_problems wikiPageWikiLink Boolean_satisfiability_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Category:Mathematics-related_lists.
- Karps_21_NP-complete_problems wikiPageWikiLink Category:NP-complete_problems.
- Karps_21_NP-complete_problems wikiPageWikiLink Clique_cover_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Clique_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Combinatorics.
- Karps_21_NP-complete_problems wikiPageWikiLink Computational_complexity_theory.
- Karps_21_NP-complete_problems wikiPageWikiLink Computational_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Computer_science.
- Karps_21_NP-complete_problems wikiPageWikiLink Conjunctive_normal_form.
- Karps_21_NP-complete_problems wikiPageWikiLink Cook–Levin_theorem.
- Karps_21_NP-complete_problems wikiPageWikiLink David_Zuckerman_(mathematician).
- Karps_21_NP-complete_problems wikiPageWikiLink Exact_cover.
- Karps_21_NP-complete_problems wikiPageWikiLink Feedback_arc_set.
- Karps_21_NP-complete_problems wikiPageWikiLink Feedback_vertex_set.
- Karps_21_NP-complete_problems wikiPageWikiLink Graph_coloring.
- Karps_21_NP-complete_problems wikiPageWikiLink Graph_theory.
- Karps_21_NP-complete_problems wikiPageWikiLink Hamiltonian_path_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Independent_set_(graph_theory).
- Karps_21_NP-complete_problems wikiPageWikiLink Integer_programming.
- Karps_21_NP-complete_problems wikiPageWikiLink Job_shop_scheduling.
- Karps_21_NP-complete_problems wikiPageWikiLink Knapsack_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink List_of_NP-complete_problems.
- Karps_21_NP-complete_problems wikiPageWikiLink Many-one_reduction.
- Karps_21_NP-complete_problems wikiPageWikiLink Maximum_cut.
- Karps_21_NP-complete_problems wikiPageWikiLink NP-completeness.
- Karps_21_NP-complete_problems wikiPageWikiLink P_versus_NP_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Partition_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Richard_M._Karp.
- Karps_21_NP-complete_problems wikiPageWikiLink Set_cover_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Set_packing.
- Karps_21_NP-complete_problems wikiPageWikiLink Steiner_tree_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Stephen_Cook.
- Karps_21_NP-complete_problems wikiPageWikiLink Subset_sum_problem.
- Karps_21_NP-complete_problems wikiPageWikiLink Time_complexity.
- Karps_21_NP-complete_problems wikiPageWikiLink Vertex_cover.
- Karps_21_NP-complete_problems wikiPageWikiLinkText "21 Problems to be NP-complete".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "21 different problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "21 diverse combinatorial and graph theoretical problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "Karp's 21 '''NP'''-complete problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "Karp's 21 NP-complete problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "Karp's original 21 NP-complete problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "Richard Karp's original 21 problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "first problems shown to be NP-complete".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "list of 21 NP-complete problems".
- Karps_21_NP-complete_problems wikiPageWikiLinkText "many problems".
- Karps_21_NP-complete_problems wikiPageUsesTemplate Template:Cite_book.
- Karps_21_NP-complete_problems wikiPageUsesTemplate Template:Cite_journal.
- Karps_21_NP-complete_problems wikiPageUsesTemplate Template:Sfn.
- Karps_21_NP-complete_problems subject Category:Mathematics-related_lists.
- Karps_21_NP-complete_problems subject Category:NP-complete_problems.
- Karps_21_NP-complete_problems hypernym Set.
- Karps_21_NP-complete_problems type List.
- Karps_21_NP-complete_problems type List.
- Karps_21_NP-complete_problems type Redirect.
- Karps_21_NP-complete_problems comment "In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete.".
- Karps_21_NP-complete_problems label "Karp's 21 NP-complete problems".
- Karps_21_NP-complete_problems sameAs Q1734364.
- Karps_21_NP-complete_problems sameAs Karps_21_NP-vollständige_Probleme.
- Karps_21_NP-complete_problems sameAs Lista_de_21_problemas_NP-completos_de_Karp.
- Karps_21_NP-complete_problems sameAs ۲۱_مسئله_انپی-کامل_کارپ.
- Karps_21_NP-complete_problems sameAs 21_problèmes_NP-complets_de_Karp.
- Karps_21_NP-complete_problems sameAs 21_problemi_NP-completi_di_Karp.
- Karps_21_NP-complete_problems sameAs Karps_21_NP-volledige_problemen.
- Karps_21_NP-complete_problems sameAs m.06d_qs.
- Karps_21_NP-complete_problems sameAs 21_NP-полная_задача_Карпа.
- Karps_21_NP-complete_problems sameAs Karpov_21_NP-kompletan_problem.
- Karps_21_NP-complete_problems sameAs 21_NP-повна_задача_Карпа.
- Karps_21_NP-complete_problems sameAs Q1734364.
- Karps_21_NP-complete_problems sameAs 卡普的二十一個NP-完全問題.
- Karps_21_NP-complete_problems wasDerivedFrom Karps_21_NP-complete_problems?oldid=698180492.
- Karps_21_NP-complete_problems isPrimaryTopicOf Karps_21_NP-complete_problems.