CS 476 – 9.

Complexity

1 Complexity Theory
What are the problems that can or cannot be solved efficiently?

Definition The running time, or time complexity of a deterministic Turing Machine (DTM) M is a function
f : N → N, where f (n) is the maximum number of steps M takes on any input of length n.

Definition The time complexity of a non-deterministic Turing Machine (NTM) M is a function f : N → N,

such that any branch of computation of M on any input of size n takes a maximum of f (n) steps.


3 




 
NTM 



 7 


f (n) ≥ DT M ≤ f (n)
 

 3 7 







3 


Remark It actually suffices to consider only the accepting paths when measuring the time complexity f (n)
since any computation that takes longer than f (n) can safely be rejected.

Definition P is the class of languages that are accepted by some polynomial-time DTM.

Definition NP (non-deterministically polynomial) is the class of languages that are accepted by some
polynomial-time NTM.

2 P vs NP
Is P = NP?

NP NP P

P ⊂ NP P = NP
3 NP-Completeness
The “hardest” problems of NP.

NP-H ARD

NP-C

NP

Definition A language L is NP-C OMPLETE if:

• L ∈ NP, and

• Every language in NP can be reduced to L through a poly-time reduction, i.e. L is NP-H ARD.
(A ≤P L, ∀A ∈NP)

NP-C

A
NP

Remark If L is NP-C OMPLETE, and L has a poly-time solution (L ∈P), then P = NP.

Remark If L is NP-C OMPLETE, and L ≤P L0 for some L0 ∈NP, then L0 is NP-C OMPLETE.

4 Polynomial-Time Reduction
Definition A “computable function” f : Σ∗ → Σ∗ is a function such that a TM M on input w halts with
f (w) on its tape.

Definition A function f is “polynomial-time computable” if it is computable by some poly-time DTM.

Definition Language A is “polynomial-time reducible” to language B (A ≤P B) if a poly-time computable

function f : Σ∗ → Σ∗ exists such that, ∀w ∈ Σ∗ ,

w ∈ A ⇐⇒ f (w) ∈ B

Σ∗ f Σ∗

A B

“Mapping Reducible”
A ≤P B

Remark Our previous reduction from ET M to EQT M is a mapping reduction.

2
5 Additional remarks and definitions
5.1 Decision vs. Optimization
• P, NP deal with decidable languages (i.e., decision problems).

• But more general problems (e.g., optimization) usually have some decision version. For example,
“what is the shortest path between x and y?” vs. “is there a path between x and y shorter than n?”

• If the decision version is “intractable”, then certainly so is the optimization version.

5.2 Encodings and “size of the input”

• An integer is assumed to be encoded in O(log n) characters.

• A graph G = (V, E) can be encoded in O(E log V ) characters.

6 The first NP-C OMPLETE language

S AT= {< Φ > | Φ is a Boolean formula that is satisfiable}

Remark A satisfiable Boolean formula is a Boolean formula that has a satisfying assignment (i.e. that
evaluates to 1).

Example Φ = (x ∧ y) ∨ (x ∧ z) is satisfiable.
e.g. x = 0, y = 1, z = 1; or x = 1, y = 1, z = 0, etc.

Example Φ = x ∧ x is not satisfiable.

Theorem 6.1 Cook-Levin Theorem, 1971: S AT is NP-C OMPLETE.

Proof Proof has two parts:

1. S AT ∈ NP.
This is easy. An NTM can test every possible assignment; or, a DTM can verify a possible solution.

2. S AT ∈ NP-H ARD.
See the excerpt from the book posted on the course web page (Cook-Levin-Theorem.pdf).

7 More NP-C OMPLETE languages

Richard Karp, 1972.

7.1 3-S AT
3-S AT= {< Φ > | Φ is a Boolean formula in “3-CNF” that is satisfiable}

Definition CNF: Conjunctive Normal Form. A list of O R clauses connected by A ND, such as:

(. . . ∨ . . . ∨ . . .) ∧ (. . . ∨ . . .) ∧ (. . . ∨ . . . ∨ . . . ∨ . . .)
3-CNF: each clause consists of 3 literals.

Example
Φ = (x1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ x5 ∨ x1 )

Fact: Every Boolean formula can be converted into 3-CNF in polynomial time.

3
Theorem 7.1 3-S AT is NP-C OMPLETE.

Proof Proof has two parts:

1. 3-S AT ∈ NP.
This is easy. An NTM can test every possible assignment; or, a DTM can verify a possible solution.

2. 3-S AT ∈ NP-H ARD.

S AT ≤P 3-S AT by the fact given above.

7.2 C LIQUE
A clique is a fully connected undirected graph.

2-clique
3-clique 4-clique

C LIQUE= {< G, k > | G contains a k-clique}

Instance: Graph G = (V, E), positive integer k.

Question: Does G contain a k-clique?

Theorem 7.2 C LIQUE is NP-C OMPLETE.

Proof Proof has two parts:

1. C LIQUE ∈ NP.
An NTM can test every possible subsets of k vertices to see whether it is a clique or not.

2. C LIQUE ∈ NP-H ARD.

3-S AT ≤P C LIQUE. See below.

A given 3-S AT instance can be converted into a C LIQUE instance as follows:

Let Φ = C1 ∧ C2 ∧ . . . ∧ Ck .
Generate a graph G = (V, E):

• Generate a vertex for each literal of each clause Ci .

• Draw an edge between two vertices x and y if:

– x and y are not in the same clause.

– x and y are not contradictory (i.e., not like x = x1 ). y = x1 .

Also take k = number of clauses in Φ.

G has a k-clique if and only if Φ has a satisfying assignment:

• If G has a k-clique, that clique must have one vertex from each clause which are not contradictory. If
we set these literals to 1 in Φ, it will be a satisfying assignment for Φ.

• If Φ has a satisfying assignment, that assignment must contain at least one literal from each clause set
to 1. If we choose one such literal from each clause and take its vertex, they will make a k-clique in
G.

Hence, 3-S AT ≤P C LIQUE. Therefore, C LIQUE is NP-C OMPLETE.

4
Example Let Φ = (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x4 ∨ x2 )
| {z } | {z } | {z }
c1 c2 c3

c2

G: x1 x2 x3

x1 x1

c1 x2 x4 c3

x3 x2

k=3

7.3 I NDEPENDENT-S ET
Definition Independent set is a subset of vertices in a graph with no edges between them.

Example Given the following graph

1 2

G: {2,3,4} is an independent set in G.

3 4

I NDEPENDENT-S ET= {< G, k > | G contains k independent vertices}

Instance: Graph G = (V, E), positive integer k.

Question: Does G contain k independent vertices?

Theorem 7.3 I NDEPENDENT-S ET is NP-C OMPLETE.

Proof Proof has two parts:

1. I NDEPENDENT-S ET ∈ NP.
An NTM can test every possible subsets of k vertices to see whether they are independent or not.

2. I NDEPENDENT-S ET ∈ NP-H ARD.

C LIQUE ≤P I NDEPENDENT-S ET. See below.

5
 For a given graph G = (V, E) consider its complement G0 = (V, E) where an edge (x, y) is in E if and
only if it is not in E. For example:

1 2 1 2

G: G’:

3 4 3 4
Claim: A vertex subset V 0 ⊆ V is a clique in G if and only if it is an independent set in G0 .
Regarding C LIQUE ≤P I NDEPENDENT-S ET, given a C LIQUE instance G = (V, E) and k, generate an
I NDEPENDENT-S ET instance G0 = (V, E) and k. G0 has an independent set of size k if and only if G
has a k-clique. Furthermore, they must be the same set of vertices V 0 . Therefore, I NDEPENDENT-S ET is
NP-C OMPLETE.

7.4 V ERTEX -C OVER

Definition Vertex cover is a subset of vertices that “cover” all the edges.
Example See the following graphs

1 2

G1 : {1} is a a vertex cover.

3 4

1 2

G2 : {1,3} is a a vertex cover.

3 4

V ERTEX -C OVER= {< G, k > | G has a vertex cover with k vertices}

Instance: Graph G = (V, E), positive integer k.
Question: Does G contain a cover with k vertices?
Theorem 7.4 V ERTEX -C OVER is NP-C OMPLETE.
Proof Proof has two parts:
1. V ERTEX -C OVER ∈ NP.
An NTM can test every possible subsets of k vertices to see whether they cover all edges or not.
2. V ERTEX -C OVER ∈ NP-H ARD.
I NDEPENDENT-S ET ≤P V ERTEX -C OVER. See below.
Observe that V 0 ⊆ V is a vertex cover if and only if V − V 0 is an independent set. For example:

1 2

G: {1,3} is a a vertex cover. {2,4} is an independent set.

3 4

Regarding I NDEPENDENT-S ET ≤P V ERTEX -C OVER, for a given independent set instance < G, k >,
generate the vertex cover instance < G, n − k >, where n = |V |. G has k independent vertices if and only
if G has a vertex cover of size n − k. Therefore V ERTEX -C OVER is NP-Complete.

6
7.5 S UBSET-S UM
Instance: a set of positive integer weights (not necessarily distinct) and a positive integer “target” t:

S = {w1 , w2 , . . . , wk } and target t

Question: Does S 0 ⊆ S exist such that:
X
w=t
w∈S 0

Theorem 7.5 S UBSET-S UM is NP-C OMPLETE.

Proof Proof has two parts:

1. S UBSET-S UM ∈ NP.
An NTM can test every possible subsets of S to see whether their summation equals the target or not.

2. S UBSET-S UM ∈ NP-H ARD.

3-S AT ≤P S UBSET-S UM. See below.

Given a 3-S AT instance Φ with n variables x1 , x2 , . . . , xn and k clauses C1 , C2 , . . . , Ck , generate a

S UBSET-S UM problem with a set S with 2n + 2k elements:

• For each variable xi , generate two elements yi and zi in S - one for xi and one for xi .

• For each clause Ci , generate two variables gi and hi .

Each of these elements will be (n + k)-digit integers with digits (d1 d2 d3 . . . dn e1 e2 . . . ek ).

These integers are defined as follows:

• yi and zi has the digit di set to 1. Also if xi appears in Cj , yi has ej set to 1. Similarly if xi appears
in Cj , zi has ej set to 1.

• gi and hi have the digit ei set to 1.

• All remaining digits are 0.

The target integer t has:

• di = 1 for all di .

• ei = 3 for all ei .

7
Example
Φ = (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x4 ∨ x2 )

d1 d2 d3 d4 e1 e2 e3
y1 1 0 0 0 0 1 0
z1 1 0 0 0 1 0 1
y2 1 0 0 0 1 0
z2 1 0 0 1 0 1
y3 1 0 1 1 0
z3 1 0 0 0 0
y4 1 0 0 1
z4 1 0 0 0
g1 1 0 0
h1 1 0 0
g2 1 0
h2 1 0
g3 1
h3 1
t 1 1 1 1 3 3 3

Let S 0 = {z1 , y2 , y3 , y4 , g1 , g2 , g3 }.
X
w = 1, 000, 101 + 100, 010 + 10, 110 + 1, 001 + 100 + 10 + 1 = 1, 111, 333
w∈S 0

This corresponds to:

x1 = x2 = x3 = x4 = 1
which satisfies Φ.

S 0 ⊆ S with weight t exists if and only if Φ has a satisfying assignment.

7.6 PARTITION
Instance: S = {w1 , w2 , ..., wk }

Question: Does S 0 ⊆ S exist such that:

X X
w = w
w∈S 0 / 0
w∈S

Theorem 7.6 PARTITION is NP-C OMPLETE.

Proof Proof has two parts:

1. PARTITION ∈ NP
An NTM can test all possible subsets of S to check whether it is a partition or not.

2. PARTITION ∈ NP-H ARD

S UBSET-S UM ≤p PARTITION See below.

8
Example Given a S UBSET-S UM problem S = {1, 3, 5}, t = 6 generate a new set S2 = {1, 3, 5, 3}. Here
we add 3. (3=2t − W , where W is the total weight of elements in S)

S2 has an equal partition:

S20 = {1, 5}, S200 = {3, 3}

The subset without the new element is the S 0 ⊆ S with weight t = 6.

w
How about t < 2?

Example Given S{1, 3, 5}, t = 4, generate:

S2 = {1, 3, 5, 1} (1 = w − 2t)

If S2 has an equal partition, take the subset with the new element and remove it:
S20 = {1, 3, 1}, S200 = 5

Showing S UBSET-S UM ≤p PARTITION:

Given a S UBSET-S UM instance

S = {w1 , w2 , ..., wk }, target t, generate the PARTITION instance as

S2 = {w1 , w2 , ..., wk , wk+1 } where wk+1 = |2t − W | and W denotes the total weight of S.

Claim: S2 has an equal partition ⇐⇒ S has subset with total weight t.

7.7 K NAPSACK
Instance: S = {x1 , x2 , ..., xk } within a weight function w : S → N+ , a value function v : S → N+ a
weight limit W , a value limit V .

Question: Does S 0 ⊆ S exist such that

X X
w(x) ≤ W, v(x) ≥ V
x∈S 0 x∈S 0

Theorem 7.7 K NAPSACK is NP-C OMPLETE.

Proof Proof has two parts:

1. K NAPSACK ∈ NP
An NTM can pick an arbitrary subset S 0 and check whether it satisfies the weight and value limits in
polynomial time.

2. K NAPSACK ∈ NP-H ARD

S UBSET-S UM ≤p K NAPSACK. See below.

For a given S UBSET-S UM instance S = {w1 , w2 , ..., wk } and t, construct the K NAPSACK instance
S2 = {x1 , x2 , ..., xk } with w(xi ) = v(xi ) = wi and W = V = t.

Obviously, S2 has a subset that satisfies the weight and value limits ⇐⇒ S has a subset S 0 with total
weight equal to t.

9
7.8 D IRECTED H AMILTONIAN C IRCUIT
Definition A Directed Hamiltonian Circuit in a directed graph is a cycle that visits every vertex in the graph
exactly once.

Instance: A directed graph G = (V, E)

Question: Does G contain a Directed Hamiltonian Circuit?

Example The following graph contains a Directed Hamiltonian Circuit.

1 2

G: 1→2→3→4→1

3 4

Theorem 7.8 D IRECTED -H AMILTONIAN -C IRCUIT is NP-C OMPLETE.

Proof Proof has two parts:

1. D IRECTED -H AMILTONIAN -C IRCUIT ∈ NP

An NTM can try every possible cycle starting from any node to check whether it is a Directed Hamil-
tonian Circuit or not.

2. D IRECTED -H AMILTONIAN -C IRCUIT is NP-H ARD

3-S AT ≤P D IRECTED -H AMILTONIAN -C IRCUIT
(proof is in the book)

7.9 H AMILTONIAN -C IRCUIT

Instance: A graph G = (V, E) (Note: If we do not sat if a graph is directed or not, it is undirected.)

Question: Does G contain a H AMILTONIAN -C IRCUIT?

Theorem 7.9 H AMILTONIAN -C IRCUIT is NP-C OMPLETE.

Proof Proof has two parts:

1. H AMILTONIAN -C IRCUIT ∈ NP
An NTM can try every possible cycle in the graph to check whether it is a Hamiltonian Circuit.

2. H AMILTONIAN -C IRCUIT ∈ NP-H ARD

D IRECTED -H AMILTONIAN -C IRCUIT ≤P H AMILTONIAN -C IRCUIT. See below.

G1 1

G01 1’ 1”
2 3

G01 1 2’ 3’
We lost direction
information
2 3 2” 3”

10
 G02 1’ 1”

G2 1 2’ 3’

2 3 2” 3”

Here we notice that with only two points for each G03 1’ 1” 1”’
vertex we find a H AMILTONIAN -C IRCUIT for this.
This is because we can’t preserve atomic structure
of a vertex. Add a point in between.
2’ 3’
G3 1
2” 3”

2 3 2”’ 3”’

For a given D IRECTED -H AMILTONIAN -C IRCUIT instance, directed graph G = (V, E), construct an
undirected graph G0 = (V 0 , E 0 ) as follows:

V 0 = {v 0 , v 00 , v 000 : v ∈ V }

E 0 = {(v 0 , v 00 ), (v 00 , v 000 ) : v ∈ V } ∪ {(v 000 , u0 ) : (v, u) ∈ E}

Claim: G has a D IRECTED -H AMILTONIAN -C IRCUIT ⇐⇒ G0 has a H AMILTONIAN -C IRCUIT.

Proof Exercise (Explained in the book).

7.10 T RAVELING S ALESMAN P ROBLEM

Instance: Graph G = (V, E) with a weight (distance function) w : E → N+ , distance limit k.

Question: Does G contain a traveling salesman cycle with a total distance (weight) no more than k?

Theorem 7.10 T RAVELING -S ALESMAN -P ROBLEM is NP-C OMPLETE.

Proof Proof has two parts:

1. T RAVELING -S ALESMAN -P ROBLEM ∈ NP

An NTM can generate an arbitrary ordering of the vertices and check whether that makes a traveling
salesman tour with total weight k or less.

2. T RAVELING -S ALESMAN -P ROBLEM ∈ NP-H ARD

H AMILTONIAN -C IRCUIT ≤P T RAVELING -S ALESMAN -P ROBLEM. See below.

We can convert any H AMILTONIAN -C IRCUIT into T RAVELING -S ALESMAN -P ROBLEM as follows:

11
 1
1 2

1 1 k = 4 (|V |)
1
3 4
1
H AMILTONIAN -C IRCUIT ≤p T RAVELING -S ALESMAN -P ROBLEM

For a given H AMILTONIAN -C IRCUIT instance G = (V, E) make it a weighted graph G0 by assigning
each edge the unit weight 1 and set k = |v|.

Obviously, G has a H AMILTONIAN -C IRCUIT ⇐⇒ G’ has a T RAVELING -S ALESMAN -P ROBLEM tour

with total weight |w|.

12