Introduction to NP-Completeness and Complexity Theory
Explore the concepts of NP-completeness, reductions, and the complexity classes P and NP in computational complexity theory. Learn about decision problems, Boolean functions, languages, polynomial-time Turing machines, and examples of problems in class P. Understand how to deal with functional problems within class P.
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 2: Class NP, Reductions, NP-completeness Indian Institute of Science
Complexity classes P and NP
Recap: Decision Problems In the initial part of this course, we ll focus primarily on decision problems. Decision problems can be naturally identified with boolean functions, i.e. functions from {0,1}* to {0,1}. Boolean functions can be naturally identified with sets of {0,1} strings, also called languages.
Recap: Decision Problems Decision problems Boolean functions Languages Definition. We say a TM M decides a language L {0,1}* if M computes fL, where fL(x) = 1 if and only if x L.
Recap: Complexity Class P Let T: N N be some function. Definition: A language L is in DTIME(T(n)) if there s a TM that decides L in time O(T(n)). Defintion: Class P = DTIME (nc). c > 0 Deterministic polynomial-time
Complexity Class P : Examples Cycle detection Solvabililty of a system of linear equations Perfect matching Primality testing (AKS test 2002) Check if a number is prime
Polynomial time Turing Machines Definition. A TM M is a polynimial time TM if there s a polynomial function q: N input x {0,1}*, M halts within q(|x|) steps. N such that for every Polynomial function. q(n) = nc for some constant c
Class (functional) P What if a problem is not a decision problem? Like the task of adding two integers.
Class (functional) P What if a problem is not a decision problem? Like the task of adding two integers. One way is to focus on the i-th bit of the output and make it a decision problem. (Is the i-th bit, on input x, 1?)
Class (functional) P What if a problem is not a decision problem? Like the task of adding two integers. One way is to focus on the i-th bit of the output and make it a decision problem. Alternatively, we define a class called functional P.
Class (functional) P What if a problem is not a decision problem? Like the task of adding two integers. One way is to focus on the i-th bit of the output and make it a decision problem. We say that a problem or a function f: {0,1}* {0,1}* is in FP (functional P) if there s a polynomial-time TM that computes f.
Complexity Class FP : Examples Greatest Common Divisor (Euclid ~300 BC) Given two integers a and b, find their gcd.
Complexity Class FP : Examples Greatest Common Divisor Counting paths in a DAG (homework) Find the number of paths between two vertices in a directed acyclic graph.
Complexity Class FP : Examples Greatest Common Divisor Counting paths in a DAG Maximum matching (Edmonds 1965) Find a maximum matching in a given graph
Complexity Class FP : Examples Greatest Common Divisor Counting paths in a DAG Maximum matching Linear Programming (Khachiyan 1979, Karmarkar 1984) Optimize a linear objective function subject to linear (in)equality constraints
Complexity Class NP Solving a problem is generally harder than verifying a given solution to the problem.
Complexity Class NP Solving a problem is generally harder than verifying a given solution to the problem. Class NP captures the set of decision problems whose solutions are efficiently verifiable.
Complexity Class NP Solving a problem is generally harder than verifying a given solution to the problem. Class NP captures the set of decision problems whose solutions are efficiently verifiable. Nondeterministic polynomial-time
Complexity Class NP Definition. A language L {0,1}* is in NP if there s a polynomial function p: N TM M (called the verifier) such that for every x, N and a polynomial time x L u {0,1}p(|x|) s.t. M(x, u) = 1
Complexity Class NP Definition. A language L {0,1}* is in NP if there s a polynomial function p: N TM M (called the verifier) such that for every x, N and a polynomial time x L u {0,1}p(|x|) s.t. M(x, u) = 1 u is called a certificate or witness for x (w.r.t L and M) if x L
Complexity Class NP Definition. A language L {0,1}* is in NP if there s a polynomial function p: N TM M (called the verifier) such that for every x, N and a polynomial time x L u {0,1}p(|x|) s.t. M(x, u) = 1 It follows that verifier M cannot be fooled!
Complexity Class NP Definition. A language L {0,1}* is in NP if there s a polynomial function p: N TM M (called the verifier) such that for every x, N and a polynomial time x L u {0,1}p(|x|) s.t. M(x, u) = 1 Class NP contains those problems (languages) which have such efficient verifiers.
Class NP : Examples Vertex cover Given a graph G and an integer k, check if G has a vertex cover of size k.
Class NP : Examples Vertex cover 0/1 integer programming Given a system of linear (in)equalities with integer coefficients, check if there s a 0-1 assignment to the variables that satisfy all the (in)equalities.
Class NP : Examples Vertex cover 0/1 integer programming Integer factoring Given 2 numbers n and U, check if n has a nontrivial factor less than equal to U.
Class NP : Examples Vertex cover 0/1 integer programming Integer factoring Graph isomorphism Given 2 graphs, check if they are isomorphic
Is P = NP ? Obviously, P NP. Whether or not P = NP is an outstanding open question in mathematics and TCS!
Is P = NP ? Obviously, P NP. Whether or not P = NP is an outstanding open question in mathematics and TCS! Solving a problem does seem harder than verifying its solution, so most people believe that P NP.
Is P = NP ? Obviously, P NP. Whether or not P = NP is an outstanding open question in mathematics and TCS! P = NP has many weird consequences, and if true, will pose a serious threat to secure and efficient cryptography.
Is P = NP ? Obviously, P NP. Whether or not P = NP is an outstanding open question in mathematics and TCS! Mathematics has gained much from attempts to prove such negative statements Galois theory, Godel s incompleteness, Fermat s Last Theorem, Turing s undecidability, Continuum hypothesis etc.
Is P = NP ? Obviously, P NP. Whether or not P = NP is an outstanding open question in mathematics and TCS! Complexity theory has several of such intriguing unsolved questions.
Polynomial time reduction Definition. We say a language L1 {0,1}* is polynomial time (Karp) reducible to a language L2 {0,1}* if there s a polynomial time computable function f s.t. x L1 f(x) L2 f(L1) L1 L2 L2 L1 f(L1)
Polynomial time reduction Definition. We say a language L1 {0,1}* is polynomial time (Karp) reducible to a language L2 {0,1}* if there s a polynomial time computable function f s.t. x L1 f(x) L2 Notation. L1 p L2 Observe. If L1 p L2 and L2 p L3 then L1 p L3 .
NP-completeness Definition. A language L is NP-hard if for every L in NP, L pL . Further, L is NP-complete if L is in NP and is NP-hard. Observe. If L is NP-hard and L is in P then P = NP. If L is NP-complete then L in P if and only if P = NP. Hardest problems inside NP in the sense that if one NPC problem is in P then all problems in NP is in P. NPC NP P
NP-completeness Definition. A language L is NP-hard if for every L in NP, L pL . Further, L is NP-complete if L is in NP and is NP-hard. Observe. If L is NP-hard and L is in P then P = NP. If L is NP-complete then L in P if and only if P = NP. Exercise. Let L1 {0,1}* be any language and L2 be a language in NP. If L1 p L2 then L1 is also in NP.
Few words on reductions As to how we define a reduction from one language to the other (or one function to the other) is usually guided by a question on whether two complexity classes are different or identical. For polynomial time reductions, the question is whether P equals NP. Reductions help us define complete problems (the hardest problems in a class) which in turn help us compare the complexity classes under consideration.
Class P and NP : Examples Vertex cover (NP-complete) 0/1 integer programming (NP-complete) Integer factoring (unlikely to be NP-complete) Graph isomorphism (Quasi-P) Primality testing (P) Linear programming (P)
How to show existence of an NPC problem? Let L = { ( , x, 1m, 1t ) : there exists a u {0,1}m s.t. M accepts (x, u) in t steps } Observation. L is NP-complete. The language L involves Turing machine in its definition. Next, we ll see an example of an NP-complete problem that is arguably more natural.
A natural NP-complete problem Definition. A boolean formula on variables x1, , xn consists of AND, OR and NOT operations. e.g. = (x1 x2) (x3 x2 ) Definition. A boolean formula is satisfiable if there s a {0,1}-assignment to its variables that makes evaluate to 1.
A natural NP-complete problem Definition. A boolean formula is in Conjunctive Normal Form (CNF) if it is an AND of OR of literals. e.g. = (x1 x2) (x3 x2 ) clauses
A natural NP-complete problem Definition. A boolean formula is in Conjunctive Normal Form (CNF) if it is an AND of OR of literals. e.g. = (x1 x2) (x3 x2 ) literals
A natural NP-complete problem Definition. A boolean formula is in Conjunctive Normal Form (CNF) if it is an AND of OR of literals. e.g. = (x1 x2) (x3 x2 ) Definition. Let SAT be the language consisting of all satisfiable CNF formulae.
A natural NP-complete problem Definition. A boolean formula is in Conjunctive Normal Form (CNF) if it is an AND of OR of literals. e.g. = (x1 x2) (x3 x2 ) Definition. Let SAT be the language consisting of all satisfiable CNF formulae. Theorem. (Cook-Levin) SAT is NP-complete.
A natural NP-complete problem Definition. A boolean formula is in Conjunctive Normal Form (CNF) if it is an AND of OR of literals. e.g. = (x1 x2) (x3 x2 ) Definition. Let SAT be the language consisting of all satisfiable CNF formulae. Theorem. (Cook-Levin) SAT is NP-complete. Easy to see that SAT is in NP. Need to show that SAT is NP-hard.
Cook-Levin theorem: Proof Main idea: Computation is local; i.e. every step of computation looks at and changes only constantly many bits; and this step can be implemented by a small CNF formula.
Cook-Levin theorem: Proof Main idea: Computation is local; i.e. every step of computation looks at and changes only constantly many bits; and this step can be implemented by a small CNF formula. Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT
Cook-Levin theorem: Proof Main idea: Computation is local; i.e. every step of computation looks at and changes only constantly many bits; and this step can be implemented by a small CNF formula. Let L NP. We intend to come up with a polynomial time computable function f: x x s.t., x L x SAT Notation: | x| := size of x = number of or in x
Cook-Levin theorem: Proof Language L has a poly-time verifier M such that x L u {0,1}p(|x|) s.t. M(x, u) = 1
