\(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

\(\left( \sum_{j=1}^P [\text{if } T_{\pi(1)} + \dots + T_{\pi(j)} \gt D_{\pi(j)} \text{ then } P_{\pi(j)} \text{ else } 0]\right) \le k .\)

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

\(\sum_{h \in I} c_h = \sum_{h \notin I} c_h\)

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

\(\sum_{\{u, v\} \in A, u \in S v \notin S} w(\{u, v\}) \ge W.\)

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]\)