Chapter 12: Complexity J;i 353
12.5 SAT IS NP-COMPLETE
In this section, we prove that the satisfiability problem for boolean expressions
(whether a boolean expression is satisfiable) is NP-complete. This is the first
problem to be proved NP-complete. Cook proved this theorem in 1971.
12.5.1 BOOLEAN EXPRESSIONS
In Section 1.1.2, we defined a well-formed formula involving propositional
variables. A boolean expression is a well-formed formula involving boolean
variables x, y, z replacing propositions P, Q, R and connectives v, 1\ and -,.
The truth value of a boolean expression in x, y, z is determined from the truth
values of x, y, z and the truth tables for v, 1\ and -,. For example, -, x 1\ -,
(y V ~) is a boolean expression. The expression -, x 1\ -, (y V z) is true when
x is false, y is false and ~ is false.
Defmition 12.10 (a) A truth assignment t for a boolean expression E is the
assignment of truth values T or F to each of the variables in E. For example,
t = (F, F, F) is a truth assignment for (x, y, ~) where .Y, y, Z are the variables
in a boolean expression E(x, y, ~) = -, X 1\ -, (y V ~).
The value E(t) of the boolean expression E given a truth assignment t is
the truth value of the expression of E, if the truth values give by t are assigned
to the respective vmiables.
If t = (F, F, F) then the truth values of -, x and -, (y v z) are T and T.
Hence the value of E = -, X /\ -, (v V z) is T. So E(t) = T.
Definition 12.11 A truth assignment t satisfies a boolean expression E if the
truth value of E(l) is T. In other words, the truth assignment t makes the
expression E true.
Defmition 12.12 A boolean expression E is satisfiable if there exists at least
one truth assignment t that satisfies E (that is E(t) = T). For example, E =
-, X 1\ -, (y V ~) is satisfiable since E(t) = T when t = (F, F, F).
12.5.2 CODING A BOOLEAN EXPRESSION
The symbols in a boolean expression are the variables .Y, y, z, etc. the
connectives v. /\, -,. and parantheses ( and ). Thus a boolean expression in
three variables will have eight distinct symbols. The variables are written as
Xl' x~, X3- etc. Also we use X" only after using XI, x~, ... , X,,_I for variables.
We encode a boolean expression as follows:
1. The variables Xl, x~, x3' ... are written as xl, xlO, ;d 1. .. _etc. (The
binary representation of the subscript is written after x.)
2. The connectives v, /\, -', (, and ) are retained in the encoded
expresslOn.
12.5 SAT IS NP-COMPLETE
In this section, we prove that the satisfiability problem for boolean expressions
(whether a boolean expression is satisfiable) is NP-complete. This is the first
problem to be proved NP-complete. Cook proved this theorem in 1971.
12.5.1 BOOLEAN EXPRESSIONS
In Section 1.1.2, we defined a well-formed formula involving propositional
variables. A boolean expression is a well-formed formula involving boolean
variables x, y, z replacing propositions P, Q, R and connectives v, 1\ and -,.
The truth value of a boolean expression in x, y, z is determined from the truth
values of x, y, z and the truth tables for v, 1\ and -,. For example, -, x 1\ -,
(y V ~) is a boolean expression. The expression -, x 1\ -, (y V z) is true when
x is false, y is false and ~ is false.
Defmition 12.10 (a) A truth assignment t for a boolean expression E is the
assignment of truth values T or F to each of the variables in E. For example,
t = (F, F, F) is a truth assignment for (x, y, ~) where .Y, y, Z are the variables
in a boolean expression E(x, y, ~) = -, X 1\ -, (y V ~).
The value E(t) of the boolean expression E given a truth assignment t is
the truth value of the expression of E, if the truth values give by t are assigned
to the respective vmiables.
If t = (F, F, F) then the truth values of -, x and -, (y v z) are T and T.
Hence the value of E = -, X /\ -, (v V z) is T. So E(t) = T.
Definition 12.11 A truth assignment t satisfies a boolean expression E if the
truth value of E(l) is T. In other words, the truth assignment t makes the
expression E true.
Defmition 12.12 A boolean expression E is satisfiable if there exists at least
one truth assignment t that satisfies E (that is E(t) = T). For example, E =
-, X 1\ -, (y V ~) is satisfiable since E(t) = T when t = (F, F, F).
12.5.2 CODING A BOOLEAN EXPRESSION
The symbols in a boolean expression are the variables .Y, y, z, etc. the
connectives v. /\, -,. and parantheses ( and ). Thus a boolean expression in
three variables will have eight distinct symbols. The variables are written as
Xl' x~, X3- etc. Also we use X" only after using XI, x~, ... , X,,_I for variables.
We encode a boolean expression as follows:
1. The variables Xl, x~, x3' ... are written as xl, xlO, ;d 1. .. _etc. (The
binary representation of the subscript is written after x.)
2. The connectives v, /\, -', (, and ) are retained in the encoded
expresslOn.