Advanced Algorithms and Complexity :
Lecture 3
Polynomial Time Reductions. The Complexity
Classes NP-Complete and NP-Hard. The
Satisfiability Problem.
August 8, 2018
Polynomial Time Reductions: We say that a language L1 reduces to
a language L2 in polynomial-time (denoted as L1 ≤p L2 ) if there exists a
polynomial-time computable function f (x) (there exists a DTM which takes
as inputs a string x and gives as output the string f (x)) such that x ∈ L1 =⇒
f (x) ∈ L2 .
If L1 ≤p L2 and L2 has a polynomial-time algorithm A2 , then we can com-
bine A2 and f to get a polynomial time algorithm A1 for L1 as follows:
1
First x is given as input to the DTM for computing f (x) in polynomial-
time. Then f (x) is given as input to DTM A2 . If A2 accepts f (x), then
A1 accepts x. If A2 rejects f (x), then A1 rejects x. The total time taken is
polynomial since both DTM’s take polynomial-time. The DTM A1 accepts
L1 because x ∈ L1 ⇐⇒ f (x) ∈ L2 .
Polynomial-time reductions are transitive: If L1 ≤p L2 , and L2 ≤p L3 , then
L1 ≤p L3 .
L1 ≤p L2 =⇒ ∃ a polynomial-time DTM computing f such that x ∈
L1 ⇐⇒ f (x) ∈ L2 .
L2 ≤p L3 =⇒ ∃ a polynomial-time DTM computing g such that y ∈
L2 ⇐⇒ g(y) ∈ L3 .
Putting y = f (x), we get: x ∈ L1 ⇐⇒ f (x) ∈ L2 ⇐⇒ g(f (x)) ∈ L3 . Since
f (x) can be computed in polynomial-time, |f (x)| is of polynomial-length and
also because g(y) can be computed in polynomial-time, (gof )(x) can be com-
puted in polynomial time =⇒ L1 ≤p L3 .
NP-Complete: A language L1 ∈ N P is called completed for N P , or NP-
complete if ∀L ∈ N P , L ≤p L1 .
NP-Hard: A Language L2 is called hard for N P , or NP-Hard if ∀L ∈ N P ,
L ≤p L2 .
The definitions of NP-complete and NP-Hard are similar, with only one differ-
ence: NP-Complete language should belong to N P , but NP-Hard Language
may not be in N P .
An NP-Complete Language is always NP-Hard, but an NP-Hard Language
may not be NP-Complete. It is unknown whether P = N P , or P 6= N P .
Usually it is believed that P 6= N P . Earlier we have seen that P ⊆ N P . We
also have the relations NP-Complete ⊆ N P , and NP-Complete 6⊆ NP-Hard.
One possibility is:
2
An NP-Complete Language is called complete for N P because a polynomial-
time algorithm for the NP-complete language can be combined with the
polynomial-time reduction to get a polynomial-time algorithm for any prob-
lem in N P (as we have seen earlier):
L ∈ NP-complete and L ∈ P =⇒ P = N P .
An NP-Hard Language is called hard for N P bacause it may be “harder”
than any problem in N P (it doesn’t belong to NP-complete). As before, if we
are able to find a polynomial-time algorithm for an NP-Hard problem, then
we can combine it with the polynomial-time reduction to get a polynomial-
time algorithm for any problem in N P :
L ∈ NP-Hard and L ∈ P =⇒ P = N P .
A Boolean Formula over the variables u1 , u2 , ..., un consists of the vari-
ables and the logical operators AND (∧), OR (∨) and NOT(¬).
Example: (u1 ∧ u2 ) ∨ (u2 ∧ u3 ) ∨ (u3 ∧ u1 ). If Φ is a Boolean formula over
variables u1 , u2 , ..., un , and z ∈ {0, 1}n , then Φ(z) denotes the value of Φ
when the variables of Φ are assigned the values z. (1 = True, 0 = False). A
formula Φ is satisfiable if there exists some assignment z such that Φ(z) is
true. Otherwise, we say that Φ is unsatisfiable.
Example: The formula x ∧¬ x ( = 0 ) is not satisfiable.
A Boolean formula over variables u1 , u2 , ..., un is in CNF form (Conjunctive
Normal Form) if it is an AND of OR’s of variables or their negation. Exam-
ple of a 3CNF formula: (u1 ∨ u2 ∨ u3 ) ∧ (u2 ∨ u3 ∨ u4 ) ∧ (u1 ∨ u3 ∨ u4 ).
More generally, a CNF formula has the form: ∧i (∨j vij ) where each vij is
either a variable uk or is negation uk . The terms ∨j vij are called its clauses.
A kCNF formula is a CNF formula in which all clauses contain at most k
literals. We denote by SAT the language of all satisfiable CNF formulae and
by 3SAT the language of all satisfiable 3CNF formulae.
3
SAT is NP-Complete (Cook-Levin Theorem): SAT ∈ NP-Complete
can be proved in two steps:
1. SAT ∈ N P : Given a Boolean formula Φ(z) as input, the NTM N will
guess an assignment of variables (0 or 1) for z, and then it will evaluate Φ(z)
in polynomial time. If Φ(z) evaluates to 1, then N will accept, oherwise it
will reject.
2. SAT ∈ NP-Hard: For this we will have to prove that for any L ∈ N P ,
L ≤p SAT. We will have to describe a polynomial-time DTM M such that:
x ∈ L =⇒ M (x) ∈ SAT and
x∈/ L =⇒ M (x) ∈ / SAT.
L ∈ N P =⇒ ∃ a polynomial time DTM D such that:
x ∈ L =⇒ ∃y ∈ {0, 1}p(|x|) such that D(x, y) = 1
x∈/ L =⇒ ∀y ∈ {0, 1}p(|x|) , D(x, y) = 0
First (unsuccessful) attempt in designing M : M will take input x, and it will
simulate D(x, y) for all y ∈ {0, 1}p(|x|) . If for any such y it gets 1 as output,
then it will output x ∧ x (∈ SAT), otherwise it will output x ∧ ¬x (∈ / SAT).
M will take exponential-time. M will be a polynomial-time DTM only for
the case of L ∈ P (|y| = 0).
