8.2. 8.2 NP-completeness

The theory of NP-completeness provides methods to prove lower bounds for problems in NP. An NP problem is said to be complete in NP if it belongs to the hardest problems in this class, i.e., if it is at least as hard as any NP problem. The complexity of two given problems can be compared by polynomial-time reductions. Among the different types of reduction one can consider, we focus on the polynomial-time many-one reducibility in this section. In Section 8.4, more general reducibilities will be introduced, such as the polynomial-time Turing reducibility and the polynomial-time (strong) nondeterministic Turing reducibility.

Definition 8.4 (Reducibility, NP-Completeness) A set is reducible to a set (in symbols, ) if and only if there exists a polynomial-time computable function such that for all , . A set is said to be -hard for NP if and only if for each set . A set is said to be -complete in NP (NP-complete, for short) if and only if is -hard for NP and .

Reductions are efficient algorithms that can be used to show that problems are not efficiently solvable. That is, if one can efficiently transform a hard problem into another problem via a reduction, the hardness of the former problem is inherited by the latter problem. At first glance, it might seem that infinitely many efficient algorithms are required to prove some problem NP-hard, namely one reduction from each of the infinitely many NP problems to . However, an elementary result says that it is enough to find just one such reduction, from some NP-complete problem . Since the -reducibility is transitive (see Exercise 8.2-2), the NP-hardness of implies the NP-hardness of via the reduction for each NP problem .

In 1971, Stephen Cook found a first such NP-complete problem: the satisfiability problem of propositional logic, for short. For many NP-completeness result, it is useful to start from the special problem , the restriction of the satisfiability problem in which each given Boolean formula is in conjunctive normal form and each clause contains exactly three literals. is also NP-complete.

Definition 8.5 (Satisfiability problem) The Boolean constants false and true are represented by and . Let be Boolean variables, i.e., for each . Variables and their negations are called literals. A Boolean formula is satisfiable if and only if there is an assignment to the variables in that makes the formula true. A Boolean formula is in conjunctive normal form (CNF, for short) if and only if is of the form , where the are literals over . The disjunctions of literals are called the clauses of . A Boolean formula is in -CNF if and only if is in CNF and each clause of contains exactly literals. Define the following two problems:

Example 8.2 (Boolean formulas) Consider the following two satisfiable Boolean formulas (see also Exercise 8.2-1:

Here, is in 3-CNF, so is in . However, is not in 3-CNF, since the first clause contains four literals. Thus, is in but not in .

Theorem 8.6 states the above-mentioned result of Cook.

Theorem 8.6 (Cook) The problems and are NP-complete.

The proof that is NP-complete is omitted. The idea is to encode the computation of an arbitrary NP machine running on input into a Boolean formula such that is satisfiable if and only if accepts .

is a good starting point for many other NP-completeness results. In fact, in many cases it is very useful to start with its restriction . To give an idea of how such proofs work, we now show that , which implies that is NP-complete. To this end, we need to find a reduction that transforms any given Boolean formula in CNF into another Boolean formula in -CNF (i.e., with exactly three literals per clause) such that

Let be the given formula with clauses . Construct the formula from as follows. The variables of are

• 's variables and

• for each clause of , a number of additional variables as needed, where depends on the structure of according to the case distinction below.

Now, define , where each clause of is constructed from the clause of as follows. Suppose that , where each is a literal over . Distinguish the following four cases.

• If , define

• If , define .

• If , define , i.e., the th clause remains unchanged.

• If , define

It remains to show that (a) the reduction is polynomial-time computable, and (b) the equivalence (8.1) is true. Both claims are easy to see; the details are left to the reader as Exercise 8.2-4.

Thousands of problems have been proven NP-complete by now. A comprehensive collection can be found in the work of Garey und Johnson [].

Exercises

8.2-1 Find a satisfying assignment each for the Boolean formulas and from Example 8.2.

8.2-2 Show that the -reducibility is transitive: .

8.2-3 Prove that is in NP.

8.2-4 Consider the reduction . Prove the following:

a. the reduction is polynomial-time computable, and

b. the equivalence (8.1) holds.