Cook–Levin theorem

theorem that Boolean satisfiability is NP-complete and therefore that NP-complete problems exist
rdfs:label
"Cook–Levin theorem"@en
skos:altLabel
"Cook's theorem"@en
schema:description
"theorem that Boolean satisfiability is NP-complete and therefore that NP-complete problems exist"@en
schema:dateModified "2024-11-11T16:59:33+00:00"^^xsd:dateTime
schema:version 2273321304
wikibase:identifiers 3
wikibase:sitelinks 21
wikibase:statements 11
p:P1136 wd:statement/Q377276-08c05c34-4837-c807-9d3d-e413e5b6254e
p:P138 wd:statement/Q377276-6c9a9e62-4254-1443-f895-23cef6baf399
wd:statement/Q377276-a423fe2f-4869-c231-5116-097bcb37437b
p:P2579 wd:statement/Q377276-d710ac25-4784-dfad-4870-be866463244a
p:P31 wd:statement/Q377276-e7448f94-4b38-da37-21e7-265fec738745
p:P361 wd:statement/Q377276-2DB677D8-96B4-4003-AA97-CA42C7BEB7FC
p:P373 wd:statement/Q377276-4f2e5fbc-a0bd-4d9e-850e-709d59f4e0fc
p:P5106 wd:statement/Q377276-108DE2FA-D223-4489-99F3-76CF143FDA02
p:P6104 wd:statement/Q377276-20F5EB4A-5ACB-4F57-A01F-E5A15B447C2F
p:P6366 wd:statement/Q377276-79E73FB6-8ABB-492D-870A-EB9FAC4445D6
p:P646 wd:statement/Q377276-DF737E08-AB06-409E-8B6B-C2EB2D12929A
p:direct-normalized/P6366 <https://makg.org/entity/206602144>
wdt:P1136 Leonid Levin
wdt:P138 Stephen Cook
Leonid Levin
wdt:P2579 computational complexity theory
wdt:P31 theorem
wdt:P361 list of theorems
wdt:P373 "Cook-Levin theorem"
wdt:P5106 "cookstheorem"
wdt:P6104 WikiProject Mathematics
wdt:P6366 "206602144"
wdt:P646 "/m/030tgp"
Download as:
TurtleJSON-LDRDF/XML
data from SPARQL profile: Wikidata