\(NP\)-completeness is a property of some computational problems, which makes them amongst the hardest computational problems, and also at least as hard as each other.

## Definition

A *decision problem* is a problem with a yes/no answer (or 0/1, true/false).

*Polynomial time* is a running time for an algorithm which is some polynomial multiplied by the size of the algorithm’s

inputs \(N\), such as \(N\), \(log\ N\), \(N\ log\ N\), \(N^2\), or \(N^3\), but *not* \(2^N\) or \(N!\).

A *deterministic algorithm* is one which, when it has to pursue several options, needs to pursue them one at a time.

A *nondeterministic algorithm* is one which, when it has to pursue several options, can pursue them simultaneously.

A nondeterministic algorithm is *faster* than a deterministic algorithm, but it is no more *powerful* in the sense of

being able to solve problems that a deterministic algorithm can’t.

The class \(P\) is the class of decision problems that can be solved in polynomial time by a deterministic algorithm.

The class \(NP\) is the class of decision problems that can be solved in polynomial time by a nondeterministic algorithm.

It follows from this that \(P\) is a subset of \(NP\).

A *polynomial reduction* is an polynomial time algorithm that can transform an instance of a problem \(A\)

(decision or otherwise) into an instance of another problem \(B\), such that the solution is preserved, i.e., for every

instance of \(A\), if the solution of \(A\) is yes, then the instance of \(B\) produced by the polynomial transformation will also

be yes, and the same for no, or any other value.

A problem (decision or otherwise) is \(NP\)-hard if every problem in \(NP\) can be reduced to it by a polynomial reduction.

So \(NP\)-hard can be read as “at least as hard as \(NP\)“.

A problem is \(NP\)-complete if it is \(NP\)-hard and it is in \(NP\).

So a problem is \(NP\)-hard but not \(NP\)-complete if it isn’t in \(NP\).

There are two two reasons for this:

1. It isn’t a decision problem, which means it isn’t in \(NP\)

2. It isn’t decidable, e.g., the Turing machine Halting Problem is \(NP\)-hard, but not in \(NP\) because the definition of \(NP\)

requires there is an algorithm, but by definition no algorithm exists for undecidable problems.

Since every problem in \(NP\) can be reduced to any \(NP\)-complete problem, but the converse is not true, the \(NP\)-complete

problems can be seen as the hardest problems in \(NP\).

Most scientists believe that there is no polynomial time algorithm that can solve an \(NP\)-hard problem.

This means that there are problems in \(NP\) that are not in \(P\), so \(P \neq NP\).

This is the \(P-NP\) Problem.

## Karp’s 21 Problems

Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” demonstrated the \(NP\)-completeness of 20 problems by reducing the known \(NP\)-complete problem **SATISFIABILITY** directly or indirectly to them as in the following diagram:

### Problem definitions

#### SATISFIABILITY

**INPUT:** Clauses \(C_1, C_2, \dots, C_p\)

**PROPERTY:** The conjunction of the given clauses is satisfiable;

i.e., there is a set \(S \subseteq \{x_1, x_2, \dots, x_n;\overline{x_1}, \overline{x_2}, \dots, \overline{x_n}\}\) such

that

a) \(S\) does not contain a complementary pair of literals and

b) \(S \cap C_k \neq \emptyset, k = 1, 2, \dots, p\)

#### 2. 0-1 INTEGER PROGRAMMING

**INPUT:** Integer matrix \(C\) and integer vector \(d\)

**PROPERTY:** There exists a \(0-1\) vector \(x\) such that \(C_x\) = \(d\).

#### 3. CLIQUE

**INPUT:** Graph \(G\), positive integer \(k\)

**PROPERTY:** \(G\) has a set of \(k\) mutually adjacent nodes.

#### 4. SET PACKING

**INPUT:** Family of sets \(\{S_j\}\), positive integer \(\ell\)

**PROPERTY:** \(\{S_j\}\) contains \(\ell\) mutually disjoint sets.

#### 5. NODE COVER

**INPUT:** Graph \(G^\prime\), positive integer \(\ell\)

**PROPERTY:** There is a set \(R \subseteq N^\prime\) such that \(|R| \le \ell\) and

every arc is incident with some node in \(R\).

#### 6. SET COVERING

**INPUT:** Finite family of finite sets \(\{S_j\}\)

**PROPERTY:** There is a subfamily \(\{T_h\} \subseteq \{S_j\}\) containing \(\le k\)

sets such that \(\bigcup T_h = \bigcup S_j\).

#### 7. FEEDBACK NODE SET

**INPUT:** Digraph \(H\), positive integer \(k\)

**PROPERTY:** There is a set \(R \subseteq V\) such that every (directed)

cycle of \(H\) contains a node in \(R\).

#### 8. FEEDBACK ARC SET

**INPUT:** Digraph \(H\), positive integer \(k\)

**PROPERTY:** There is a set \(S \subseteq E\) such that every (directed)

cycle of \(H\) contains an arc in \(S\).

#### 9. DIRECTED HAMILTON CIRCUIT

**INPUT:** Digraph \(H\)

**PROPERTY:** \(H\) has a directed cycle which includes each node exactly once.

#### 10. UNDIRECTED HAMILTON CIRCUIT

**INPUT:** Graph \(G\)

**PROPERTY:** \(G\) has a cycle which includes each node exactly once.

#### 11. SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE

**INPUT:** Clauses \(D_1, D_2, \ldots, D_r\), each consisting of at most 3

literals from the set \(\{u_1, u_2, \ldots, u_m\} \cup \{\overline{u_1}, \overline{u_2}, \ldots, \overline{u_m}\}\)

**PROPERTY:** The set {\(D_1, D_2, \ldots, D_r\)} is satisfiable.

#### 12. CHROMATIC NUMBER

**INPUT:** Graph \(G\), positive integer \(k\)

**PROPERTY:** There is a function \(\phi: N \to \mathbb{Z_k}\) such that, if \(u\)

and \(v\) are adjacent, then \(\phi(u) \ne \phi(v)\).

#### 13. CLIQUE COVER

**INPUT:** Graph \(G\), positive integer \(\ell\)

**PROPERTY:** \(N^\prime\) is the union of \(\ell\) or fewer cliques.

#### 14. EXACT COVER

**INPUT:** Family \(\{S_j\}\) of subsets of a set \(\{u_i, i = 1, 2, \ldots, t\}\)

**PROPERTY:** There is a subfamily \(\{T_h\} \subseteq \{S_j\}\) such that the

sets \(T_h\) are disjoint and \(\bigcup T_h = \bigcup S_j = \{u_i, i = 1, 2, \ldots, t\}\).

#### 15. HITTING SET

**INPUT:** Family \(\{U_i\}\) of subsets of \(\{S_j, j = 1, 2, \ldots, r\}\)

**PROPERTY:** There is a set \(W\) such that, for each \(i\), \(|W \cap U_i| = 1\).

#### 16. STEINER TREE

**INPUT:** Graph \(G\), \(R \subseteq N\), weighting function \(w: A \to \mathbb{Z}\),

positive integer k

**PROPERTY:** \(G\) has a subtree of weight \(\leq k\) containing the set of nodes in \(R\).

#### 17. 3-DIMENSIONAL MATCHING

**INPUT:** Set \(U \subseteq T \times T \times T\), where \(T\) is a finite set

**PROPERTY:** There is a set \(W \subseteq U\) such that \(|W| = |T|\) and

no two elements of \(W\) agree in any coordinate.

#### 18. KNAPSACK

**INPUT:** \((a_1, a_2, \ldots, a_r, b) \in \mathbb{Z}^{n+1}\)

**PROPERTY:** \(\sum a_j x_j = b\) has a \(0-1\) solution.

#### 19. JOB SEQUENCING

**INPUT:**

“execution time vector” \((T_1, \ldots, T_P) \in \mathbb{Z}^P\)

“deadline vector” \((D_1, \ldots, D_P) \in \mathbb{Z}^P\)

“penalty vector” \((P_1, \ldots, P_P) \in \mathbb{Z}^P\)

positive integer \(k\)

**PROPERTY:** There is a permutation \(\pi\) of \(\{1, 2, \ldots, P\)} such that

#### 20. PARTITION

**INPUT:** \((c_1, c_2, \ldots, c_s) \in \mathbb{Z}^S\)

**PROPERTY:** There is a set \(I \subseteq \{1, 2, \ldots, s\}\) such that

#### 21. MAX CUT

**INPUT:** graph \(G\), weighting function \(w: A \to \mathbb{Z}\), positive

integer \(W\)

**PROPERTY:** There is a set \(S \subseteq N\) such that

### Reductions

#### SATISIFIABILITY \(\propto\) 0,1 INTEGER PROGRAMMING

\(c_{ij} = \begin{cases} 1 & if\; x_j \in C_i\quad i=1, 2, \dots, p \\

-1 & if\; \overline{x_j} \in C_i\quad i=1, 2, \dots, n \\

0 & otherwise\; \end{cases}\)

The vector \(b\) is dimension \(p\) with:

\(b_i\) = 1 – (the number of complemented variables in \(C_i\)),

\(i = 1, 2, \ldots, p\).

#### SATISFIABILITY \(\propto\) CLIQUE

\(N = \{\langle \sigma, i\rangle | \sigma\) is a literal and occurs in \(C_i\}\)

\(A = \{\{\langle \sigma, i\rangle, \langle\delta, j\rangle\} | i \neq j\) and \(\sigma \neq \overline{\delta}\}\)

\(k = p\), the number of clauses

#### CLIQUE \(\propto\) SET PACKING

Assume \(N = \{1, 2, \ldots, n\}\).

The elements of the sets \(S_1, S_2, \ldots, S_n\) are those two-element sets of nodes \(\{i, j\}\) not in \(A\).

\(S_i = \{\{i, j\}| \{i, j\} \notin A\}, i = 1, 2, \ldots, n\).

\(\ell = k\).

#### CLIQUE \(\propto\) NODE COVER

\(G^\prime\) is the complement of \(G\).

\(\ell = |N| – k\).

#### NODE COVER \(\propto\) SET COVERING

Assume \(N^\prime = \{0, 1, \ldots, n\}\).

The elements are the arcs of \(G^\prime\).

\(S_j\) is the set of arcs incident with node \(j\).

\(k = \ell\).

#### NODE COVER \(\propto\) FEEDBACK NODE SET

\(V = N^\prime\).

\(E = \{\langle u, v\rangle | \{u,v\} \in A^\prime\}\).

\(k = \ell\).

#### NODE COVER \(\propto\) FEEDBACK ARC SET

\(V = N^\prime \times \{0, 1\}\).

\(E = \{\langle \langle u, 0 \rangle, \langle u, 1 \rangle \rangle| u \in N^\prime\} \cup \{\langle \langle u, 1\rangle, \langle v, 0\rangle\rangle| \{u, v\} \in A^\prime\}\).

\(k = \ell\).

#### NODE COVER \(\propto\) DIRECTED HAMILTONIAN CIRCUIT

Without loss of generality assume \(A^\prime = Z_m\).

\(V = \{a_1, a_2, \dots, a_\ell\} \cup \{\langle u, i, \alpha \rangle\ | u \in N^\prime\) is incident with \(i \in A^\prime\) and \(\alpha \in \{0, 1\}\}\)

\(E = \{\langle \langle u, i, 0 \rangle, \langle u, i, 1 \rangle, \rangle | \langle u, i, 0 \rangle \in V\}\)

\(\;\cup\;\{\langle \langle u, i, \alpha \rangle, \langle v, i, \alpha \rangle \rangle | i \in A^\prime, u\) and \(v\) are incident with \(i\), \(\alpha \in \{0, 1\}\}\)

\(\;\cup\;\{\langle \langle u, i, 1 \rangle, \langle u, j, 0 \rangle \rangle | u\) is incident with \(i\) and \(j\) and \(!\exists h, i \lt h \lt j,\) such that \(u\) is incident with \(h\}\)

\(\;\cup\;\{\langle \langle u, i, 1 \rangle, a_f \rangle | 1 \leq f \leq \ell\) and \(!\exists h \gt i\) such that \(u\) is incident with \(h\}\)

\(\;\cup\;\{\langle a_f,\langle u, i, 0 \rangle \rangle | 1 \leq f \leq \ell\) and \(!\exists h \lt i\) such that \(u\) is incident with \(h\}\)

#### DIRECTED HAMILTONIAN CIRCUIT \(\propto\) UNDIRECTED HAMILTONIAN CIRCUIT

\(N = V \times \{0, 1, 2\}\)

\(A = \{\{\langle u, 0 \rangle, \langle u, 1\}, \{\langle u, 1 \rangle, \langle u, 2 \rangle\}| u \in V\}\)

\(\; \cup \{\{\langle u, 2 \rangle, \langle v, 0 \rangle\} | \langle u, v \rangle \in E\}\)

#### SATISFIABILITY \(\propto\) SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE

Replace a clause \(\sigma_1 \cup \sigma_2 \cup \ldots \cup \sigma_m\), where the \(\sigma_i\) are literals and \(m \gt\) 3, by

\((\sigma_1 \cup \sigma_2 \cup u_1)(\sigma_3 \cup \ldots \cup \sigma_m \cup \overline{u_1})(\overline{\sigma_3} \cup u_1) \ldots (\overline{\sigma_m} \cup u_1)\),

where \(u_1\) is a new variable.

Repeat this transformation until no clause has more than three literals.

#### SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE \(\propto\) CHROMATIC NUMBER

Assume without loss of generality that \(m \ge 4\).

\(N = \{u_1, u_2, \ldots, u_m\} \cup \{\overline{u1}, \overline{u2}, \ldots, \overline{um}\} \cup {v1, v2, \ldots, v_m}\)

\(\;\cup \{D_1, D_2, \dots, D_r\}\)

\(A = \{\{u_i, \overline{ui}\}| i = 1, 2, \ldots, n\} \cup \{\{v_i, v_j\} | i \neq j\} \cup \{\{v_i, x_j\}| i != j\} \cup \{\{v_i, \overline{x_j}\}| i \neq j\}\)

\(\;\cup \{\{u_i, D_f\} | u_i \notin D_f\} \cup \{\{\overline{u_i}, D_f\}| \overline{u_i} \in D_f\}\)

\(k = r + 1\)

#### CHROMATIC NUMBER \(\propto\) CLIQUE COVER

\(G^\prime\) is the complement of \(G\)

\(\ell = k\)

#### CHROMATIC NUMBER \(\propto\) EXACT COVER

The set of elements is

\(N \cup A \cup \{ \langle u, e, f\rangle | u\) is incident with \(e\) and \(1 \leq f \leq k\}\).

The sets \(S_j\) are the following:

for each \(f, 1 \leq f \leq k\), and each \(u \in N\),

\(\quad\{u\} \cup \{\langle u, e, f \rangle | e\) is incident with \(u\}\);

for each \(e \in A\) and each pair \(f_1, f_2\) such that

\(\quad 1 \leq f_1 \leq k, 1 \leq f_2 \leq k\) and \(f_1 \neq f_2\)

\(\quad\{e\} \cup \{\langle u, e, f \rangle, f \neq f_1\} \cup \{\langle v, e, g \rangle | g \neq f_2\}\),

where \(u\) and \(v\) are the two nodes incident with \(e\).

#### EXACT COVER \(\propto\) HITTING SET

The hitting set problem has sets \(U_i\) and elements \(s_j\) such that

\(s_j \in U_i \iff u_i \in S_j\).

#### EXACT COVER \(\propto\) STEINER TREE

\(N = \{n_0\} \cup \{S_j\} \cup \{u_1\}\)

\(R = \{n_0\} \cup \{u_i\}\)

\(A = \{\{n_0, S_j\}\} \cup \{\{S_j, u_i\}| u_i \in S_j\}\)

\(w(\{n_0, S_j\}) = |S_j|\)

\(w(\{S_j, u_i\}) = 0\)

\(k = |\{u_i\}|\).

#### EXACT COVER \(\propto\) 3-DIMENSIONAL MATCHING

Without loss of generality, assume \(|S_j| \geq 2\) for each \(j\).

Let \(T = \{\langle i, j \rangle | u_i \in S_j\}\).

Let \(\alpha\) be an arbitrary one-one function from \(\{u_i\}\) into \(T\).

Let \(pi: T \to T\) be a permutation such that,

for each fixed \(j, \{\langle i, j\rangle | u_i \in S_j\}\) is a cycle of \(\pi\).

\(U = \{\langle \alpha(u_i), \langle i, j\rangle , \langle i, j\rangle \rangle | \langle i, j\rangle \in T\}\)

\(\quad\cup \langle \beta, \sigma, \pi(\sigma)\rangle | \text{for all } i, \beta \ne \alpha(u_i)\}\).

#### EXACT COVER \(\propto\) KNAPSACK

Let \(d = |\{S_j\}|+1.\)

Let \(\epsilon_ji = \begin{cases} 1 & if\; u_i \in S_j \\

0 & if\; u_i \notin S_j \end{cases}\)

Let \(r = |\{S_j\}|, a_j = \sum \epsilon_{ji}d^{i-1}\;and\;b = \frac{d^t-1}{d-1}.\)

#### KNAPSACK \(\propto\) SEQUENCING

\(p = r, T_i = P_i = a_i, D_i = b\).

#### KNAPSACK \(\propto\) PARTITION

\(s = r + 2\)

\(c_i = a_i i = 1, 2, \ldots r\)

\(c_{r+1} = b + 1\)

\(c_{r+2} = (\sum_{i = 1}^r a_i) + 1 – b\)

#### PARTITION \(\propto\) MAX CUT

\(N = \{1, 2, \dots, s\}\)

\(A = \{\{i, j\} | i \in N, j \in N, i \ne j\}\)

\(w(\{i, j\}) = c_i \cdot c_j\)

\(W = [\frac{1}{4} \sum c_i^2]\)