DBpedia – Linked Data Fragments

Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Cook–Levin_theorem> ?p ?o }

• Cook–Levin_theorem abstract "In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.The theorem is named after Stephen Cook and Leonid Levin.An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.The question of whether such an algorithm exists is called the P versus NP problem and it is widely considered the most important unsolved problem in theoretical computer science.".
• Cook–Levin_theorem wikiPageID "663047".
• Cook–Levin_theorem wikiPageLength "14387".
• Cook–Levin_theorem wikiPageOutDegree "45".
• Cook–Levin_theorem wikiPageRevisionID "650608978".
• Cook–Levin_theorem wikiPageWikiLink Boolean_data_type.
• Cook–Levin_theorem wikiPageWikiLink Boolean_expression.
• Cook–Levin_theorem wikiPageWikiLink Boolean_satisfiability_problem.
• Cook–Levin_theorem wikiPageWikiLink Boolean_variable.
• Cook–Levin_theorem wikiPageWikiLink Category:Articles_containing_proofs.
• Cook–Levin_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
• Cook–Levin_theorem wikiPageWikiLink Complexity_class.
• Cook–Levin_theorem wikiPageWikiLink Computational_complexity_theory.
• Cook–Levin_theorem wikiPageWikiLink Conjunctive_normal_form.
• Cook–Levin_theorem wikiPageWikiLink Decision_problem.
• Cook–Levin_theorem wikiPageWikiLink Deterministic_Turing_machine.
• Cook–Levin_theorem wikiPageWikiLink If_and_only_if.
• Cook–Levin_theorem wikiPageWikiLink Karps_21_NP-complete_problems.
• Cook–Levin_theorem wikiPageWikiLink Leonid_Levin.
• Cook–Levin_theorem wikiPageWikiLink Logical_conjunction.
• Cook–Levin_theorem wikiPageWikiLink Logical_connective.
• Cook–Levin_theorem wikiPageWikiLink NP-completeness.
• Cook–Levin_theorem wikiPageWikiLink NP_(complexity).
• Cook–Levin_theorem wikiPageWikiLink NP_complete.
• Cook–Levin_theorem wikiPageWikiLink Non-deterministic_Turing_machine.
• Cook–Levin_theorem wikiPageWikiLink Non-deterministic_algorithm.
• Cook–Levin_theorem wikiPageWikiLink Nondeterministic_Turing_machine.
• Cook–Levin_theorem wikiPageWikiLink Nondeterministic_algorithm.
• Cook–Levin_theorem wikiPageWikiLink Oracle_machine.
• Cook–Levin_theorem wikiPageWikiLink P_versus_NP_problem.
• Cook–Levin_theorem wikiPageWikiLink Polynomial-time_many-one_reduction.
• Cook–Levin_theorem wikiPageWikiLink Polynomial-time_reduction.
• Cook–Levin_theorem wikiPageWikiLink Polynomial_time.
• Cook–Levin_theorem wikiPageWikiLink Reduction_(complexity).
• Cook–Levin_theorem wikiPageWikiLink Richard_Karp.
• Cook–Levin_theorem wikiPageWikiLink Richard_M._Karp.
• Cook–Levin_theorem wikiPageWikiLink Robert_M._Solovay.
• Cook–Levin_theorem wikiPageWikiLink Robert_Solovay.
• Cook–Levin_theorem wikiPageWikiLink Search_problem.
• Cook–Levin_theorem wikiPageWikiLink Soviet_Union.
• Cook–Levin_theorem wikiPageWikiLink Stephen_Cook.
• Cook–Levin_theorem wikiPageWikiLink Symposium_on_Theory_of_Computing.
• Cook–Levin_theorem wikiPageWikiLink Time_complexity.
• Cook–Levin_theorem wikiPageWikiLink Truth_value.
• Cook–Levin_theorem wikiPageWikiLink Turing_Award.
• Cook–Levin_theorem wikiPageWikiLink Turing_machine.
• Cook–Levin_theorem wikiPageWikiLink USSR.
• Cook–Levin_theorem wikiPageWikiLink File:CookLevin_svg.svg.
• Cook–Levin_theorem wikiPageWikiLinkText "Cook–Levin theorem".
• Cook–Levin_theorem wikiPageWikiLinkText "Cook–Levin theorem#Proof".
• Cook–Levin_theorem hasPhotoCollection Cook–Levin_theorem.
• Cook–Levin_theorem wikiPageUsesTemplate Template:Reflist.
• Cook–Levin_theorem subject Category:Articles_containing_proofs.
• Cook–Levin_theorem subject Category:Theorems_in_computational_complexity_theory.
• Cook–Levin_theorem comment "In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.".
• Cook–Levin_theorem label "Cook–Levin theorem".
• Cook–Levin_theorem sameAs مبرهنة_كوك_وليفين.
• Cook–Levin_theorem sameAs Satz_von_Cook.
• Cook–Levin_theorem sameAs Teorema_de_Cook.
• Cook–Levin_theorem sameAs قضیه_کوک_لوین.
• Cook–Levin_theorem sameAs Théorème_de_Cook.
• Cook–Levin_theorem sameAs משפט_קוק-לוין.
• Cook–Levin_theorem sameAs Teorema_Cook.
• Cook–Levin_theorem sameAs Teorema_di_Cook-Levin.
• Cook–Levin_theorem sameAs 쿡-레빈_정리.
• Cook–Levin_theorem sameAs Twierdzenie_Cooka.
• Cook–Levin_theorem sameAs Teorema_de_Cook-Levin.
• Cook–Levin_theorem sameAs m.030tgp.
• Cook–Levin_theorem sameAs Теорема_Кука_—_Левина.
• Cook–Levin_theorem sameAs Cook-Levinov_teorem.
• Cook–Levin_theorem sameAs Cook–Levin_theorem.
• Cook–Levin_theorem sameAs Кук-Левинова_теорема.
• Cook–Levin_theorem sameAs Cook-Levin_teoremi.
• Cook–Levin_theorem sameAs Теорема_Кука_—_Левіна.
• Cook–Levin_theorem sameAs Q377276.
• Cook–Levin_theorem sameAs Q377276.
• Cook–Levin_theorem sameAs Cook-Levin理論.
• Cook–Levin_theorem wasDerivedFrom Cook–Levin_theorem?oldid=650608978.
• Cook–Levin_theorem isPrimaryTopicOf Cook–Levin_theorem.