About: Cook–Levin theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Cook–Levin theorem Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin.

Attributes	Values
rdfs:label	Cook–Levin theorem (en)
rdfs:comment	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, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin. (en)
sameAs	Cook–Levin theorem
dbp:wikiPageUsesTemplate	dbt:' dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description
Subject	Articles containing proofs Theorems in computational complexity theory
thumbnail	wiki-commons:Special:FilePath/CookLevin_svg.svg?width=300
foaf:depiction
gold:hypernym	NP-complete
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Cook–Levin_theorem?oldid=1070654658&ns=0
Wikipage page ID	663047 (xsd:integer)
page length (characters) of wiki page	16720 (xsd:nonNegativeInteger)
Wikipage revision ID	1070654658 (xsd:integer)
Link from a Wikipage to another Wikipage	Logical conjunction Logical connective NP-completeness NP-completeness Nondeterministic Turing machine Nondeterministic algorithm Boolean data type Boolean expression Boolean satisfiability problem Stephen Cook Turing Award Turing machine Articles containing proofs PSPACE-complete P versus NP problem Search problem Decision problem Robert M. Solovay Time complexity Truth value Complexity class Algorithmic complexity Conjunctive normal form Oracle machine Soviet Union Theorems in computational complexity theory If and only if Karp's 21 NP-complete problems Symposium on Theory of Computing Leonid Levin Polynomial-time reduction Reduction (complexity) Richard M. Karp
has 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, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin. An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving Boolean satisfiability, then every NP problem can be solved by a deterministic polynomial-time algorithm. The question of whether such an algorithm for Boolean satisfiability exists is thus equivalent to the P versus NP problem, which is widely considered the most important unsolved problem in theoretical computer science. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Cook–Levin_theorem
is Wikipage redirect of	Cock-Levin theorem Cook-Levin theorem Cock Levin Cock–Levin theorem Cook's Theorem Cook's theorem Cook-Levin Theorem Cook levin theorem Cook theorem Proof that Boolean satisfiability problem is NP-complete
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures List of theorems NP-completeness Non-interactive zero-knowledge proof Advice (complexity) Boolean satisfiability problem History of artificial intelligence Circuit satisfiability problem List of mathematical logic topics List of multiple discoveries Clique problem Cock-Levin theorem Complexity and Real Computation Algorithmic complexity Cook-Levin theorem List of Russian IT developers List of Russian mathematicians List of Russian scientists List of University of Toronto faculty List of computability and complexity topics Karp's 21 NP-complete problems Karp–Lipton theorem Descriptive Complexity Hamiltonian complexity Leonid Levin Cock Levin Cock–Levin theorem Cook's Theorem Cook's theorem Cook-Levin Theorem Cook levin theorem Cook theorem
is known for of	Leonid Levin Stephen Cook
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Cook–Levin_theorem

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 1005 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software