778
Modeling Arithmetic, Computation, and Languages
inclusion is proper, that is, whether P ( NP so that there could be NP problems—
including perhaps the Hamiltonian circuit problem—that are intractable.
The Hamiltonian circuit problem belongs to a third class of problems known
as np-complete problems, meaning that not only are they in NP, but if a polynomial-time decision algorithm were ever found for any one of them, that is, if
any of them were ever found to be in P, then indeed we would have P = NP.
A large number of problems from many different fields have been found to be
NP-complete since this idea was formulated in 1971.
example 48
The problem of deciding, for an arbitrary propositional wff, whether it is a tautology is NP-complete. No efficient algorithm has been found for its solution. A
brute-force algorithm would explore each of the possible truth assignments to the
statement letters. Like the Hamiltonian circuit problem, we see the exponential
(nonpolynomial) nature of this inefficient approach—a wff with n statement letters
has a truth table with 2
n
rows. A related problem called the satisfiability problem
asks for a decision as to whether there exists any truth assignment that can “satisfy” the wff—make it true. This is also an NP-complete problem, and in fact was
the first problem discovered to be NP-complete. Its brute-force solution algorithm
also relies on testing all truth value assignments.
The graph-coloring problem (given an arbitrary graph and a positive integer k,
color the nodes of the graph using k colors so that all adjacent nodes are different
colors) is NP-complete. Again, no efficient algorithm has been found; the bruteforce approach says to assign colors to nodes so that adjacent nodes are different
colors, and if you run into a place where this becomes impossible, backtrack and
modify your color assignments. Basically, this says to try all possible color assignments (similar to trying all truth assignments, but with k
n
possibilities).
The general Sudoku puzzle consists of an n
2
× n
2
grid made up of n × n
blocks where each row, each column, and each block must contain exactly one
of the digits 1 through n
2
. (See Exercise 53 in Section 2.4 for an example of the
popular n = 3 version.) This is an NP-complete problem. No efficient solution
algorithm is known; a brute-force solution tries all possible number assignments.
Once again, no polynomial-time decision algorithm has been found for any
of these or the many other NP-complete problems, and if an efficient procedure
could be found to solve any one of them, such a procedure would exist for all
other problems in NP. Therefore it is now suspected that P ( NP and that all these
problems are intractable, but to prove this remains a tantalizing goal in computer
science research.
S e c t i o n 9 . 4 review
tecHniQueS
• Describe the action of a given Turing machine on a
given initial tape.
• Construct a Turing machine to recognize a given set.
• Construct a Turing machine to compute a given
number-theoretic function.
main iDeaS
• Turing machines have a deterministic mode of
operation, the ability to reread and rewrite input,
and an unbounded auxiliary memory.
• A finite-state machine is a special case of a Turing
machine.
W
W
Modeling Arithmetic, Computation, and Languages
inclusion is proper, that is, whether P ( NP so that there could be NP problems—
including perhaps the Hamiltonian circuit problem—that are intractable.
The Hamiltonian circuit problem belongs to a third class of problems known
as np-complete problems, meaning that not only are they in NP, but if a polynomial-time decision algorithm were ever found for any one of them, that is, if
any of them were ever found to be in P, then indeed we would have P = NP.
A large number of problems from many different fields have been found to be
NP-complete since this idea was formulated in 1971.
example 48
The problem of deciding, for an arbitrary propositional wff, whether it is a tautology is NP-complete. No efficient algorithm has been found for its solution. A
brute-force algorithm would explore each of the possible truth assignments to the
statement letters. Like the Hamiltonian circuit problem, we see the exponential
(nonpolynomial) nature of this inefficient approach—a wff with n statement letters
has a truth table with 2
n
rows. A related problem called the satisfiability problem
asks for a decision as to whether there exists any truth assignment that can “satisfy” the wff—make it true. This is also an NP-complete problem, and in fact was
the first problem discovered to be NP-complete. Its brute-force solution algorithm
also relies on testing all truth value assignments.
The graph-coloring problem (given an arbitrary graph and a positive integer k,
color the nodes of the graph using k colors so that all adjacent nodes are different
colors) is NP-complete. Again, no efficient algorithm has been found; the bruteforce approach says to assign colors to nodes so that adjacent nodes are different
colors, and if you run into a place where this becomes impossible, backtrack and
modify your color assignments. Basically, this says to try all possible color assignments (similar to trying all truth assignments, but with k
n
possibilities).
The general Sudoku puzzle consists of an n
2
× n
2
grid made up of n × n
blocks where each row, each column, and each block must contain exactly one
of the digits 1 through n
2
. (See Exercise 53 in Section 2.4 for an example of the
popular n = 3 version.) This is an NP-complete problem. No efficient solution
algorithm is known; a brute-force solution tries all possible number assignments.
Once again, no polynomial-time decision algorithm has been found for any
of these or the many other NP-complete problems, and if an efficient procedure
could be found to solve any one of them, such a procedure would exist for all
other problems in NP. Therefore it is now suspected that P ( NP and that all these
problems are intractable, but to prove this remains a tantalizing goal in computer
science research.
S e c t i o n 9 . 4 review
tecHniQueS
• Describe the action of a given Turing machine on a
given initial tape.
• Construct a Turing machine to recognize a given set.
• Construct a Turing machine to compute a given
number-theoretic function.
main iDeaS
• Turing machines have a deterministic mode of
operation, the ability to reread and rewrite input,
and an unbounded auxiliary memory.
• A finite-state machine is a special case of a Turing
machine.
W
W