|
In computational complexity theory, Cook's theorem, proved by Stephen Cook in his 1971 paper "The Complexity of Theorem Proving Procedures", states that the Boolean satisfiability problem is NP-complete.[1] Image File history File links Please see the file description page for further information. ...
It has been suggested that this article or section be merged into Cooks theorem. ...
Image File history File links Please see the file description page for further information. ...
In computational complexity theory, the Cook-Levin Theorem, proved by Stephen Cook in his 1971 paper The Complexity of Theorem Proving Procedures and independently by Leonid Levin in his 1972 paper Universal Search Problems, states that the Boolean satisfiability problem is NP-complete. ...
As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...
Stephen A. Cook is a noted computer scientist. ...
1971 (MCMLXXI) was a common year starting on Friday. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
The theorem was independently proved by Leonid Levin at about the same time, so it is sometimes called the Cook–Levin theorem.[2] Leonid Levin (born November 2, 1948, USSR) is a computer scientist. ...
Definitions
A decision problem is in NP if it can be solved by a non-deterministic algorithm in polynomial time. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In the theory of computation, a nondeterministic algorithm is an algorithm with one or more choice points where multiple different continuations are possible, without any specification of which one will be taken. ...
In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
A decision problem is NP-complete if it is in NP and if every problem in NP can be reduced to it by a polynomial-time many-one reduction. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...
An instance of the Boolean satisfiability problem is a Boolean expression that combines Boolean variables using Boolean operators. An expression is satisfiable if there is some assignment of truth values to the variables that makes the entire expression true. A Boolean expression is an expression that results in a Boolean value, that is, TRUE or FALSE. For example, the value for 5 > 3 is TRUE, the value for An apple is not a fruit is FALSE. Boolean expressions are used also in document retrieval. ...
A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ...
In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ...
In logic, a truth value, or truth-value, is a value indicating to what extent a statement is true. ...
Proof The Boolean satisfiability problem is in NP because a non-deterministic Turing machine in polynomial time can guess an assignment of truth values to the variables, determine the value of the expression under that assignment, and accept if the assignment makes the entire expression true.
Now suppose that a problem in NP is solved by the non-deterministic Turing machine M = (Q, Σ, s, F, δ) (where Q is the set of states, Σ the alphabet of tape symbols, s ∈ Q the initial state, F ⊆ Q the set of accepting states, and δ : Q × Σ → Q × Σ × {−1,+1} the set of transitions) and that M accepts or rejects an instance of the problem in time p(n) where n is the size of the instance and p is a polynomial function.
We describe for each instance I a Boolean expression which is satisfiable if and only if the machine M accepts I. It has been suggested that this article or section be merged with Logical biconditional. ...
The Boolean expression uses the variables set out in the following table, where q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, and 0 ≤ k ≤ p(n):
| Variables | Intended interpretation | How many? | | Tijk | True if tape cell i contains symbol j at step k of the computation. | O(p(n)²) | | Hik | True if the M's read/write head is at tape cell i at step k of the computation. | O(p(n)²) | | Qqk | True if M is in state q at step k of the computation. | O(p(n)) | Define the Boolean expression B to be the conjunction of the clauses in the following table, for all −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n): | Clauses | Conditions | Interpretation | How many? | | Tij0 | Tape cell i of the input I contains symbol j. | Initial contents of the tape. | O(p(n)) | | Qs0 | | Initial state of M | O(1) | | H00 | | Initial position of read/write head. | O(1) | | Tijk → ¬ Tij′k | j ≠ j′ | One symbol per tape cell. | O(p(n)²) | | Tijk = Tij(k+1) ∨ Hik | | Tape remains unchanged unless written. | O(p(n)²) | | Qqk → ¬ Qq′k | q ≠ q′ | Only one state at a time. | O(p(n)) | | Hik → ¬ Hi′k | i ≠ i′ | Only one head position at a time. | O(p(n)²) | The disjunction of the clauses
(Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1)) | (q, σ, q′, σ′, d) ∈ δ | Possible transitions at computation step k when head is at position i. | O(p(n)²) | The disjunction of the clauses
Qf(p(n)) | f ∈ F. | Must finish in an accepting state. | O(1) | If there is an accepting computation for M on input I, then B is satisfiable, by assigning Tijk, Hik and Qik their intended interpretations. On the other hand, if B is satisfiable, then there is an accepting computation for M on input I that follows the steps indicated by the assignments to the variables. Logical disjunction (usual symbol or) is a logical operator that results in true if either of the operands is true. ...
How large is B? There are O(p(n)²) Boolean variables, each of which may be encoded in space O(log p(n)). The number of clauses is O(p(n)²). So the size of B is O((log p(n)) p(n)²). This is polynomial in n, the size of the input, so the transformation is certainly a polynomial-time many-one reduction, as required.
Consequences The proof shows that any problem in NP can be reduced in polynomial time (in fact, logarithmic space suffices) to an instance of the Boolean satisfiability problem. This means that if the Boolean satisfiability problem could be solved in polynomial time by a deterministic Turing machine, then all problems in NP could be solved in polynomial time, and so the complexity class NP would be equal to the complexity class P. The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...
In computational complexity theory, a complexity class is a set of problems of related complexity. ...
Cook's theorem was the first proof of NP-completeness for any problem. Other proofs of NP-completeness generally proceed by reducing the problem from another problem that has already been shown to be NP-complete. For example, the problem 3-SAT (the satisfiability problem for Boolean expressions in conjunctive normal form with three variables or negations of variables per clause) can be shown to be NP-complete by showing how to reduce any instance of SAT to an equivalent instance of 3-SAT. The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ...
In Boolean logic, a formula is in Conjunctive Normal Form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ...
Garey and Johnson present more than 300 NP-complete problems in their book Computers and Intractability: A Guide to the Theory of NP-Completeness, and new problems are still being discovered to be within that complexity class.[3]
References - ^ Stephen Cook (1971). "The Complexity of Theorem Proving Procedures", Proceedings of the third annual ACM symposium on Theory of computing, 151–158.
- ^ Leonid Levin (1973). "Universal'nye perebornye zadachi". Problemy Peredachi Informatsii 9 (3): 265–266. English translation, "Universal Search Problems", in B. A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing 6 (4): 384-400.
- ^ Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.
|
Feeds |
Contact