The Algorithm Design Manual Second Edition

9.4

Satisfiability

To demonstrate the hardness of all problems using reductions, we must start with

a single problem that is absolutely, certifiably, undeniably hard. The mother of all

NP-complete problems is a logic problem named satisfiability:

Problem: Satisfiability

Input: A set of Boolean variables V and a set of clauses C over V .

the variables v

1

, . . . , v

n

true or false so that each clause contains at least one true

literal?

Output: Does there exist a satisfying truth assignment for C—i.e., a way to set

---

9 . 4

S A T I S F I A B I L I T Y

329

This can be made clear with two examples. Suppose that C =

{{v

1

, v

2

}, {v

1

, v

2

}}

over the Boolean variables V =

{v

1

, v

2

}. We use v

i

to denote the complement of

the variable v

i

, so we get credit for satisfying a particular clause containing v

i

if

v

i

= true, or a clause containing v

i

if v

i

= false. Therefore, satisfying a particular

set of clauses involves making a series of n true or false decisions, trying to find

the right truth assignment to satisfy all of them.

These example clauses C =

{{v

1

, v

2

}, {v

1

, v

2

}} can be satisfied by either setting

v

1

= v

2

= true or v

1

= v

2

= false. However, consider the set of clauses C =

{{v

1

, v

2

}, {v

1

, v

2

}, {v

1

}}. Here there can be no satisfying assignment, because v

1

must be false to satisfy the third clause, which means that v

2

must be false to

satisfy the second clause, which then leaves the first clause unsatisfiable. Although

you try, and you try, and you try, and you try, you can’t get no satisfaction.

For a combination of social and technical reasons, it is well accepted that satis-

fiability is a hard problem; one for which no worst-case polynomial-time algorithm

exists. Literally every top-notch algorithm expert in the world (and countless lesser

whether a given set of clauses is satisfiable. All have failed. Furthermore, many

strange and impossible-to-believe things in the field of computational complexity

have been shown to be true if there exists a fast satisfiability algorithm. Satisfia-

bility is a hard problem, and we should feel comfortable accepting this. See Section

14.10

(page

472

) for more on the satisfiability problem and its applications.