{"entities":{"Q7361443":{"pageid":31519868,"ns":120,"title":"Item:Q7361443","lastrevid":105365960,"modified":"2026-10-07T13:36:19Z","type":"item","id":"Q7361443","labels":{"en":{"language":"en","value":"The Cook-Levin theorem"}},"descriptions":{"en":{"language":"en","value":"AFP entry Cook_Levin"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"beac18e91baca80fcb7d4512f245235195f5a36e","datavalue":{"value":"https://isa-afp.org/entries/Cook_Levin.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361443$19858F10-884A-4B2F-B2EF-CA14F07C615E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9e5f837bbd739196c6522f6e0dee1c61b972cae3","datavalue":{"value":{"time":"+2023-01-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361443$503ECADD-1521-4EF3-9367-450783DE0B42","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"c880886cb635661f702d173d3e42959861580a9e","datavalue":{"value":"Frank J. Balbach","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361443$26AF2F65-6C8E-4FF3-8DE7-412D4AFED31A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e1dfc20bf822b65edfe3aa467e59a651afb5ebf","datavalue":{"value":{"text":"The Cook-Levin theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361443$36DD9347-83B7-4FDB-B162-35CB63E6B9F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d93c22326de46d9be756de1daac4dca464f7153","datavalue":{"value":"The Cook-Levin theorem states that deciding the satisfiability of Boolean formulas in conjunctive normal form is $\\mathcal{NP}$-complete. This entry formalizes a proof of this theorem based on the textbook Computational Complexity: A Modern Approach by Arora and Barak. It contains definitions of deterministic multi-tape Turing machines, the complexity classes $\\mathcal{P}$ and $\\mathcal{NP}$, polynomial-time many-one reduction, and the decision problem $\\mathtt{SAT}$. For the $\\mathcal{NP}$-hardness of $\\mathtt{SAT}$, the proof first shows that every polynomial-time computation can be performed by a two-tape oblivious Turing machine. An $\\mathcal{NP}$ problem can then be reduced to $\\mathtt{SAT}$ by a polynomial-time Turing machine that encodes computations of the problem's oblivious two-tape verifier Turing machine as formulas in conjunctive normal form.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361443$6FD82406-7DA8-451F-AEFD-0AC0BD010602","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$6D5E6E12-82AE-461A-B1C5-42CD497A2E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63782d14544341fc9bcb14dd400d4878549b2492","datavalue":{"value":{"entity-type":"item","numeric-id":1687735,"id":"Q1687735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$4F9F414B-6FE6-4FE1-9521-E6D19B38C4FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e61672816c936e2b1e5e309793c5f70986ac8cff","datavalue":{"value":{"entity-type":"item","numeric-id":5464665,"id":"Q5464665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$49D5D780-D380-43E0-8DD1-FC1918DB4489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b4dd31c7b9c10eb7577027dd1c4dd424b1676a","datavalue":{"value":{"entity-type":"item","numeric-id":6099609,"id":"Q6099609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$7C817DF1-3B50-4BB6-8378-5F3D402C28F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ed8c1c9b5cf85c3067f46e271b605235d5e997","datavalue":{"value":{"entity-type":"item","numeric-id":5339741,"id":"Q5339741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$6AF49AE2-BFFD-48C9-8B36-3063B66517BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81bc1973756de66ea2f782ba7348429e285693ab","datavalue":{"value":{"entity-type":"item","numeric-id":5915950,"id":"Q5915950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$8B735C73-16B7-4C10-8E2E-4A50FABE5D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea79bf0b8998e59df4aaa18289fafa2fe7f354f5","datavalue":{"value":{"entity-type":"item","numeric-id":3392275,"id":"Q3392275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$D4FF8E42-E0C1-4B9F-A7C9-A7E93E4A7C82","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$7AB2C79E-9DB1-4B33-BFA2-FAFD87438FA3","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"73d93a21b0749f7f2c51d7daeb11b162660cd756","datavalue":{"value":{"entity-type":"item","numeric-id":7360784,"id":"Q7360784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$07738476-0E4F-401D-9F16-36D49BB1907D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361443$EAC466B6-5E5E-413C-A5F8-F2085900562D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Cook-Levin theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Cook-Levin_theorem"}}}}}