Definition
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.
Related concepts
Annals of the History of ComputingBig O notationBoolean expressionBoolean satisfiability problemBoolean variableBoris TrakhtenbrotCommutative diagramComplexity classComputational complexity theoryComputers and IntractabilityConjunctive normal formConstructive proofDavid S. JohnsonDecision problemDeterministic Turing machineExistential quantifierIf and only ifKarp's 21 NP-complete problemsLeonid LevinLogarithmic spaceLogical conjunctionLogical connectiveMathematical logicianMichael GareyNL-completeNL (complexity)NP-completenessNP (complexity)Nondeterministic Turing machineOracle machinePSPACEPSPACE-completeP versus NP problemPolynomial-time many-one reductionPolynomial timeProceedings of the USSR Academy of SciencesQuantified Boolean formulaReduction (complexity)Richard KarpRobert SolovaySearch problemSoviet UnionStephen CookSymposium on Foundations of Computer ScienceSymposium on Theory of ComputingTheoretical computer scienceTruth valueTuring AwardUniversal quantifierW. H. Freeman and CompanyWitness (mathematics)
9 concepts already in your glossary