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