NP-Completeness

NP-completeness and the classes P and NP

Classes P

The class P consists of those problems that are solvable in polynomial time.

More specifically, they are problems that can be solved in time $O (n^{k})$ for some
constant k, where n is the size of the input to the problem.

Classes NP

The class NP consists of those problems that are “verifiable” in polynomial time.

What do we mean by a problem being verifiable? If we were somehow given a
“certificate” of a solution, then we could verify that the certificate is correct in time
polynomial in the size of the input to the problem.

NP-completeness

Informally, a problem is in the class NPC—and we refer to it as being NP-complete if
it is in NP and is as “hard” as any problem in NP.

In the meantime, we will state without proof that if any NP-complete problem
can be solved in polynomial time, then every problem in NP has a polynomialtime
algorithm.

Reference:

Polynomial time

Abstract problems

To understand the class of polynomial-time solvable problems, we must first have
a formal notion of what a “problem” is. We define an abstract problem Q to be a
binary relation on a set I of problem instances and a set S of problem solutions.
For example, an instance for SHORTEST-PATH is a triple consisting of a graph
and two vertices. A solution is a sequence of vertices in the graph, with perhaps
the empty sequence denoting that no path exists. The problem SHORTEST-PATH
itself is the relation that associates each instance of a graph and two vertices with
a shortest path in the graph that connects the two vertices. Since shortest paths are
not necessarily unique, a given problem instance may have more than one solution.

Endocing

In order for a computer program to solve an abstract problem, we must represent
problem instances in a way that the program understands. An encoding of a set S
of abstract objects is a mapping e from S to the set of binary strings.

A formal-language framework

Omit!

Exercise

Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.

Polynomial-time verification

Hamiltonian cycles

A hamiltonian cycle of an undirected graph $G = (V; E)$ is a simple cycle that contains each vertex in $V$ . A graph that contains a hamiltonian cycle is said to be hamiltonian; otherwise, it is nonhamiltonian.

We can define the hamiltonian-cycle problem, “Does a graph G have a hamiltonian cycle?” as a formal language:

H A M - C Y C L E = {(G) : G i s a h a m i l t o n i a n g r a p h}

This naive algorithm does not run in polynomial time. In fact, the hamiltonian-cycle problem is NP-complete.

Verification algorithms

We define a verification algorithm as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a certificate. A two-argument algorithm A verifies an input string x if there exists a certificate y such that $A (x, y) = 1$ . The language verified by a verification algorithm A is

L = {x \in {0, 1}^{*} : t h e r e e x i s t s y \in {0, 1}^{*} s u c h t h a t A (x, y) = 1}

The complexity class NP

Omit!

Exercises

Question 1

Prove that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian.

Answer

Let graph G be a bipartite graph with an odd number of vertices and G be Hamiltonian, meaning that there is a directed cycle that includes every vertex of G. As such, there exists a cycle in G would of odd length. However, a graph G is bipartite if and only if every cycle of G has even length. Proven by contradiction, if G is a bipartite graph with an odd number of vertices, then G is non-Hamiltonian.

Question 2

Show that any language in NP can be decided by an algorithm running in time $2^{O (n^{k})}$ for some constant k.

Answer

Question 3

A hamiltonian path in a graph is a simple path that visits every vertex exactly
once. Show that the language $H A M - P A T H = (G, u, i) : t h e r e i s a h a m i l t o n i a n p a t h f r o m u t o i i n g r a p h G$ belongs to NP.

Answer

Question 4

Show that the hamiltonian-path problem from Exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.

Answer

For this particular problem, we could find a polynomial-time solution for it and then it’s proven it could be solved in polynomial-time.

In this following step, I will give some steps that will demonstrate it will resolve the problem:

1) find a path in the original graph $G$ that in-degree is zero, because for a DAG it must have a source node that in-degree is zero. If there’re more than one nodes, then there is no solution, since every node must be visited, but the zero degree should start first and if there’re more than one point, then there must be some nodes that left cannot be visited at first.

2) remove the source node which in-degree is zero and its neighboring edges so that we could find the next node to start, let’s assume that the left graph is $G^{'}$ .

3) if the left graph $G^{'}$ has more than two nodes or vertices that have the in-degree which is zero, then we could judge that it’s unsolvable, because as I said in 1) there is no way to visit those nodes since there in-degree is zero and there should only be one to visit after its predecessor.

4) keep doing the 3) until we have reached the end-point, which there is no other nodes to visit. If there is some nodes that are not visited but we cannot find an edge to reach it, then it’s unsolvable, otherwise we should get the solution.

From the above steps, we have found the solution for the hamiltonian-path, and its complexity if $O (| E | + | V |)$ , while here $| V |$ is the number of vertices in the graph and $| E |$ is the number of edges in the graph, because we have to trace the vertices and its neighborhood edges from $v{1} $t o$ v{n}$. We know that it is done in polynomial time.

NP-completeness and reducibility

Reducibility

A language $L_{1}$ is polynomial-time reducible to a language $L_{2}$ , written $L_{1} \leq_{p} L_{2}$

If there exists a polynomial-time computable function $f :{0, 1}^ \rightarrow {0, 1}^ $s u c h t h a t f o r a l l$ x \in {0, 1}^*$,

x \in L_{1} i f a n d o n l y i f f (x) \in L_{2}

We call the function f the reduction function, and a polynomial-time algorithm F that computes f is a reduction algorithm.

NP-completeness

A language $L \in 0, 1$ is NP-complete if

$L \in N P$ , and
$L^{'} \leq_{p} L$ for every $L^{'} \in N P$ .

If a language L satisfies property 2, but not necessarily property 1, we say that L is NP-hard. We also define NPC to be the class of NP-complete languages.

Circuit satisfiability

The language CIRCUIT-SAT is therefore at least as hard as any language in NP, and since it belongs to NP, it is NP-complete.

Exercise

Question 1

Show that the $\leq_{p}$ relation is a transitive relation on languages. That is, show that if $L_{1} \leq_{p} L_{2}$ and $L_{2} \leq_{p} L_{3}$ , then $L_{1} \leq_{p} L_{3}$ .

Answer

Question 2

A language L is complete for a language class C with respect to polynomial-time reductions if $L \in C$ and $L^{'} \leq_{p} L$ for all $L^{'} \in C$ . Show that $\empty$ and ${0, 1}^{*}$ are the only languages in P that are not complete for P with respect to polynomial-time reductions.

Answer

Omit

NP-completeness proofs

Language L is NP-complete:

Prove $L \in N P$ .
Select a known NP-complete language $L^{'}$ .
Describe an algorithm that computes a function $f$ mapping every instance $x \in {0, 1}^{*}$ of $L^{'}$ to an instance $f (x)$ of $L$ .
Prove that the function $f$ satisfies $x \in L^{'}$ if and only if $f (x) \in L$ for all $x \in {0, 1}^{*}$ .
Prove that the algorithm computing $f$ runs in polynomial time.

3-CNF satisfiability

We define 3-CNF satisfiability using the following terms. A literal in a boolean formula is an occurrence of a variable or its negation. A boolean formula is in conjunctive normal form, or CNF, if it is expressed as an AND of clauses, each of which is the OR of one or more literals. A boolean formula is in 3-conjunctive normal form, or 3-CNF, if each clause has exactly three distinct literals.

Theorem

Satisfiability of boolean formulas in 3-conjunctive normal form is NP-complete.

Exercises

Question 1

Consider the straightforward (nonpolynomial-time) reduction in the proof of Theorem 34.9. Describe a circuit of size n that, when converted to a formula by this method, yields a formula whose size is exponential in n.

Answer

Question 2

Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.

Answer

NP-complete problems

What the F*!

Exercises

Question 1

The subgraph-isomorphism problem takes two undirected graphs $G_{1}$ and $G_{2}$ , and it asks whether $G_{1}$ is isomorphic to a subgraph of $G_{2}$ . Show that the subgraph-isomorphism problem is NP-complete.