∅ = ∧ ∨ ∧
= ∨
∅ =
(
) (
)
1 1
0 1
1 1
1
Therefore the Boolean formula is satisfiable.
Ì Exam ple 7.5.2: Check whether the formula
(
) (
) (
) (
)
x y
x y
x y
x y
∨ ∧ ∨ ∧ ∨ ∧ ∨
is satisfiable or not?
Solu tion
(Hint: Proceed in the same way as the previous problem).
7.6 ADDITIONAL NP PROBLEMS
The following problems have a polynomial-time solution, but an
exponential-time solution on a deterministic machine. There are literally
hundreds of additional examples.
(a) The Travelling Salesman Problem (TSP): A salesman starting in Texas,
wants to visit every capital city in the United States, returning to Texas as his
last stop. In what order should he visit the capital cities so as to minimize the
total distance travelled?
(b) The Hamiltonian Circuit Problem: Every capital city has direct air flights
to at least some capital cities. Our intrepid salesman wants to visit all the
capitals, and return to his starting point, taking only direct air flights. Can he
find a path that lets him do this?
(c) Linear Programming: We have on hand X amount of butter, Y amount of
flour, Z eggs etc. We have cookie recipies that use varying amounts of these
ingredients. Different kinds of cookies bring different prices. What mix of
cookies should we make in order to maximize profits?
7.7 NP-COMPLETE PROBLEMS
All the known NP problems have a remarkable characteristic: They are all
reducible to one another. What this means is that, given any two NP problems
X and Y,
(a) There exists a polynomial-time algorith to restate a problem of
type X as a problem of type Y, and
(b) There exists a polynomial-time algorithm to translate a solution to
a type Y problem back into a solution for the type X problem.
Complexity Theory
239
= ∨
∅ =
(
) (
)
1 1
0 1
1 1
1
Therefore the Boolean formula is satisfiable.
Ì Exam ple 7.5.2: Check whether the formula
(
) (
) (
) (
)
x y
x y
x y
x y
∨ ∧ ∨ ∧ ∨ ∧ ∨
is satisfiable or not?
Solu tion
(Hint: Proceed in the same way as the previous problem).
7.6 ADDITIONAL NP PROBLEMS
The following problems have a polynomial-time solution, but an
exponential-time solution on a deterministic machine. There are literally
hundreds of additional examples.
(a) The Travelling Salesman Problem (TSP): A salesman starting in Texas,
wants to visit every capital city in the United States, returning to Texas as his
last stop. In what order should he visit the capital cities so as to minimize the
total distance travelled?
(b) The Hamiltonian Circuit Problem: Every capital city has direct air flights
to at least some capital cities. Our intrepid salesman wants to visit all the
capitals, and return to his starting point, taking only direct air flights. Can he
find a path that lets him do this?
(c) Linear Programming: We have on hand X amount of butter, Y amount of
flour, Z eggs etc. We have cookie recipies that use varying amounts of these
ingredients. Different kinds of cookies bring different prices. What mix of
cookies should we make in order to maximize profits?
7.7 NP-COMPLETE PROBLEMS
All the known NP problems have a remarkable characteristic: They are all
reducible to one another. What this means is that, given any two NP problems
X and Y,
(a) There exists a polynomial-time algorith to restate a problem of
type X as a problem of type Y, and
(b) There exists a polynomial-time algorithm to translate a solution to
a type Y problem back into a solution for the type X problem.
Complexity Theory
239