Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Cook–Levin_theorem> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- 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 Leonid Levin and Stephen Cook.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 wikiPageRevisionID "606106877".
- 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理論".
- Cook–Levin_theorem label "Cook–Levin theorem".
- Cook–Levin_theorem label "Satz von Cook".
- Cook–Levin_theorem label "Teorema de Cook".
- Cook–Levin_theorem label "Teorema de Cook-Levin".
- Cook–Levin_theorem label "Teorema di Cook-Levin".
- Cook–Levin_theorem label "Théorème de Cook".
- Cook–Levin_theorem label "Twierdzenie Cooka".
- Cook–Levin_theorem label "Теорема Кука — Левина".
- Cook–Levin_theorem label "مبرهنة كوك وليفين".
- Cook–Levin_theorem sameAs Cook%E2%80%93Levin_theorem.
- Cook–Levin_theorem sameAs Satz_von_Cook.
- Cook–Levin_theorem sameAs Teorema_de_Cook.
- Cook–Levin_theorem sameAs Théorème_de_Cook.
- 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 Q377276.
- Cook–Levin_theorem sameAs Q377276.
- Cook–Levin_theorem wasDerivedFrom Cook–Levin_theorem?oldid=606106877.