Understanding Cook-Levin Theorem in NP-Completeness
The Cook-Levin theorem establishes the NP-completeness of the SAT language by showing how every problem in NP can be reduced to SAT. It demonstrates that computation is a local process where each step only affects a constant number of bits. Through this, a polynomial time computable function can be derived to verify solutions efficiently. The theorem's main insight lies in the transformation of problems into SAT instances, highlighting the complexity of decision versus search problems in computational complexity theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computational Complexity Theory Lecture 4: NTMs, Search vs Decision, Class co-NP Indian Institute of Science
Recap: Cook-Levin theorem Definition. Let SAT be the language consisting of all satisfiable CNF formulae. Theorem. (Cook-Levin) SAT is NP-complete.
Recap: Cook-Levin theorem Definition. Let SAT be the language consisting of all satisfiable CNF formulae. Theorem. (Cook-Levin) SAT is NP-complete. Theorem. Let N be a DTM that runs in time T(n) on inputs of length n, and outputs 0/1. Then, 1. There s a boolean circuit of size poly(T(n)) such that (u) = N(u), for every u of length n. 2. is computable in time poly(T(n)) from M. if T(n) is time constructible!
Cook-Levin theorem: Proof Main insight: Computation is local; i.e. every step of computation looks at and changes only constantly many bits. . . qi,j bi,j hi,j i cell j . . qi-1,j-1 bi-1,j-1 hi-1,j-1 qi-1,j bi-1,j hi-1,j qi-1,j+1 bi-1,j+1 hi-1,j+1 i-1 cell j-1 cell j cell j+1
Cook-Levin theorem: Proof Main insight: Computation is local; i.e. every step of computation looks at and changes only constantly many bits. . . qi,j bi,j hi,j i . . qi-1,j-1 bi-1,j-1 hi-1,j-1 qi-1,j bi-1,j hi-1,j qi-1,j+1 bi-1,j+1 hi-1,j+1 i-1 cell j-1 cell j cell j+1
Recap: Cook-Levin theorem Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Language L has a poly-time verifier M such that x L u {0,1}p(|x|) s.t. M(x, u) = 1
Recap: Cook-Levin theorem Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Language L has a poly-time verifier M such that x L u {0,1}p(|x|) s.t. x(u) = 1
Recap: Cook-Levin theorem Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Language L has a poly-time verifier M such that x L x(u) is satisfiable
Recap: Cook-Levin theorem Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Language L has a poly-time verifier M such that x L x(u) is satisfiable a poly-size circuit but not a poly-size CNF
Recap: Cook-Levin theorem Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Language L has a poly-time verifier M such that x L x(u) is satisfiable may not be possible to convert a x to a poly-size CNF x such that x(u) = x(u).
Recap: Cook-Levin theorem From circuit to CNF. From circuit construct a CNF by introducing some extra variables such that (u) = N(u) = 1 iff (u, extra variables ) is satisfiable.
Recap: Cook-Levin theorem From circuit to CNF. From circuit construct a CNF by introducing some extra variables v such that (u) = N(u) = 1 iff (u, v) is satisfiable. Language L has a poly-time verifier M such that x L u {0,1}p(|x|) s.t. x(u) = 1
Recap: Cook-Levin theorem From circuit to CNF. From circuit construct a CNF by introducing some extra variables v such that (u) = N(u) = 1 iff (u, v) is satisfiable. Language L has a poly-time verifier M such that x L u {0,1}p(|x|) s.t. x(u, v) is satisfiable
Recap: Cook-Levin theorem From circuit to CNF. From circuit construct a CNF by introducing some extra variables v such that (u) = N(u) = 1 iff (u, v) is satisfiable. Language L has a poly-time verifier M such that x L x(u, v) is satisfiable x is computable in time poly(T(n)) from M. if T(n) is time constructible!
Recap: Cook-Levin theorem From circuit to CNF. From circuit construct a CNF by introducing some extra variables v such that (u) = N(u) = 1 iff (u, v) is satisfiable. Language L has a poly-time verifier M such that x L x(u, v) is satisfiable A satisfying assignment (u, v) for x trivially gives a certificate u such that M(x, u) = 1.
Nondeterministic Turing Machines A nondeterministic Turing machine is like a deterministic Turing machines but with two transition functions. It is formally defined by a tuple ( , Q, 0 , 1). It has a special state qaccept in addition to qstart and qhalt.
Nondeterministic Turing Machines A nondeterministic Turing machine is like a deterministic Turing machines but with two transition functions. It is formally defined by a tuple ( , Q, 0 , 1). It has a special state qaccept in addition to qstart and qhalt. At every step of computation, the machine applies one of two functions 0 and 1arbitrarily. this is different from randomly
Nondeterministic Turing Machines A nondeterministic Turing machine is like a deterministic Turing machines but with two transition functions. It is formally defined by a tuple ( , Q, 0 , 1). It has a special state qaccept in addition to qstart and qhalt. At every step of computation, the machine applies one of two functions 0 and 1arbitrarily. also called nondeterministically
Nondeterministic Turing Machines A nondeterministic Turing machine is like a deterministic Turing machines but with two transition functions. It is formally defined by a tuple ( , Q, 0 , 1). It has a special state qaccept in addition to qstart and qhalt. At every step of computation, the machine applies one of two functions 0 and 1arbitrarily. Unlike DTMs, NTMs are not intended to be physically realizable (because of the arbitrary nature of application of the transition functions).
Nondeterministic Turing Machines Definition. An NTM M accepts a string x {0,1}* iff on input x there exists a sequence of applications of the transition functions 0 and 1 (beginning from the start configuration) that makes M reach qaccept. Defintion. An NTM M decides a language L {0,1}* if M accepts x x L On every sequence of applications of the transition functions on input x, M either reaches qaccept or qhalt.
Nondeterministic Turing Machines Definition. An NTM M accepts a string x {0,1}* iff on input x there exists a sequence of applications of the transition functions 0 and 1 (beginning from the start configuration) that makes M reach qaccept. Defintion. An NTM M decides a language L {0,1}* if M accepts x x L On every sequence of applications of the transition functions on input x, M either reaches qaccept or qhalt. remember in this course we ll always be dealing with TMs that halt on every input.
Nondeterministic Turing Machines Definition. An NTM M accepts a string x {0,1}* iff on input x there exists a sequence of applications of the transition functions 0 and 1 (beginning from the start configuration) that makes M reach qaccept. Defintion. An NTM M decides L in T(|x|) time if M accepts x x L On every sequence of applications of the transition functions on input x, M either reaches qaccept or qhalt within T(|x|) steps of computation.
Class NTIME Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant.
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be a language in NP. Then, there s a poly-time verifier M s.t, x L u {0,1}p(|x|) s.t. M(x, u) = 1 c > 0
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be a language in NP. Then, there s a poly-time verifier M s.t, x L u {0,1}p(|x|) s.t. M(x, u) = 1 Think of an NTM M that on input x, at first guesses a u {0,1}p(|x|) by applying 0 and 1 nondeterministically c > 0
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be a language in NP. Then, there s a poly-time verifier M s.t, x L u {0,1}p(|x|) s.t. M(x, u) = 1 c > 0 . and then simulates M on (x, u) to verify M(x,u) = 1.
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be in NTIME (nc). Then, there s an NTM M that decides L in p(n) = O(nc) time. (|x| = n) c > 0
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be in NTIME (nc). Then, there s an NTM M that decides L in p(n) = O(nc) time. (|x| = n) Think of a verifier M that takes x and u {0,1}p(n) as input, c > 0
Alternate characterization of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). Proof sketch: Let L be in NTIME (nc). Then, there s an NTM M that decides L in p(n) = O(nc) time. (|x| = n) Think of a verifier M that takes x and u {0,1}p(n) as input, and simulates M on x with u as the sequence of choices for applying 0 and 1 . c > 0
Search version of NP problems Recall: A language L {0,1}* is in NP if There s a poly-time verifier M such that x L iff there s a poly-size certificate u s.t M(x,u) = 1 Search version of L: Given an input x {0,1}*, find a u {0,1}p(|x|) such that M(x,u) = 1, if such a u exists.
Search version of NP problems Recall: A language L {0,1}* is in NP if There s a poly-time verifier M such that x L iff there s a poly-size certificate u s.t M(x,u) = 1 Search version of L: Given an input x {0,1}*, find a u {0,1}p(|x|) such that M(x,u) = 1, if such a u exists. Example: Given a 3CNF , find a satisfying assignment for if such an assignment exists.
Decision versus Search Is the search version of an NP-problem more difficult than the corresponding decision version?
Decision versus Search Is the search version of an NP-problem more difficult than the corresponding decision version? Theorem. Let L {0,1}* be NP-complete. Then, the search version of L can be solved in poly-time if and only if the decision version can be solved in poly-time.
Decision versus Search Is the search version of an NP-problem more difficult than the corresponding decision version? Theorem. Let L {0,1}* be NP-complete. Then, the search version of L can be solved in poly-time if and only if the decision version can be solved in poly-time. Proof. (search decision) Obvious.
Decision versus Search Is the search version of an NP-problem more difficult than the corresponding decision version? Theorem. Let L {0,1}* be NP-complete. Then, the search version of L can be solved in poly-time if and only if the decision version can be solved in poly-time. Proof. (decision search) We ll prove this for L = SAT first.
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable.
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn)
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn)
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) A( (0,..) ) = N
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn)
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn) A( (1,0,..) ) = Y
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn) A( (1,0,..) ) = Y (1,0,0, ,xn)
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn) A( (1,0,..) ) = Y (1,0,0, ,xn) A( (1,0,0...) ) = N
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn) A( (1,0,..) ) = Y (1,0,0, ,xn) (1,0,1, ,xn) A( (1,0,0...) ) = N
SAT is downward self-reducible Proof. (decision search) Let L = SAT, and A be a poly-time algorithm to decide if (x1, ,xn) is satisfiable. (x1, ,xn) A( ) = Y (0, ,xn) (1, ,xn) A( (0,..) ) = N A( (1,..) ) = Y (1,0, ,xn) A( (1,0,..) ) = Y (1,0,0, ,xn) (1,0,1, ,xn) A( (1,0,0...) ) = Y A( (1,0,0...) ) = N
