Reconsider the SAT problem. We made some rudimentary argument to claim
that this problem can be solved efficiently by a nondeterministic Turing machine
and, rather inefficiently, by a brute-force exponential search. A number of minor
points were ignored in that argument.
Suppose that a CNF expression has length n, with m different literals. Since
clearly m < n, we can take n as the problem size. Next, we must encode the CNF
expression as a string for a Turing machine. We can do this, for example, by
taking Σ = {x, ∨, ∧, (,), −, 0, 1} and encoding the subscript of x as a binary
number. In this system, the CNF expression
is encoded as
Since the subscript cannot be larger than m, the maximum length of any
subscript is log 2 m. As a consequence the maximum encoded length of an nsymbol CNF is O(nlogn).
The next step is to generate a trial solution for the variables.
Nondeterministically, this can be done in O(n) time. (See Exercise 1 at the end of
this section.) This trial solution is then substituted into the input string. This can
be done in O(n 2 logn) time*. The entire process therefore can be done in
O(n 2 logn))or O(n 3 ) time, and SAT ∈ NP.
There are a large number of graph problems that have been studied and are
known to be in NP.
Example 14.7
The Hamiltonian Path Problem Given an undirected graph, with vertices υ 1 ,
υ 2 ,…, υ n , a Hamiltonian path is a simple path that passes through all the vertices.
The graph in Figure 14.2 has a Hamiltonian path (υ 2 , υ 1 ), (υ 1 , υ 3 ), (υ 3 , υ 5 ), (υ 5 ,
υ 4 ), (υ 4 , υ 6 ). The Hamiltonian path problem (HAMPATH) is to decide if a given
graph has a Hamiltonian path.
A deterministic algorithm is easily found, since any Hamiltonian path is a
permutation of the vertices υ 1 , υ 2 ,…, υ n . There are n! such permuations, and a
brute-force search of all of them will give the answer. Unfortunately, this comes
at a great expense, even for modest n.
To explore the nondeterministic solution, we must first find a way to
that this problem can be solved efficiently by a nondeterministic Turing machine
and, rather inefficiently, by a brute-force exponential search. A number of minor
points were ignored in that argument.
Suppose that a CNF expression has length n, with m different literals. Since
clearly m < n, we can take n as the problem size. Next, we must encode the CNF
expression as a string for a Turing machine. We can do this, for example, by
taking Σ = {x, ∨, ∧, (,), −, 0, 1} and encoding the subscript of x as a binary
number. In this system, the CNF expression
is encoded as
Since the subscript cannot be larger than m, the maximum length of any
subscript is log 2 m. As a consequence the maximum encoded length of an nsymbol CNF is O(nlogn).
The next step is to generate a trial solution for the variables.
Nondeterministically, this can be done in O(n) time. (See Exercise 1 at the end of
this section.) This trial solution is then substituted into the input string. This can
be done in O(n 2 logn) time*. The entire process therefore can be done in
O(n 2 logn))or O(n 3 ) time, and SAT ∈ NP.
There are a large number of graph problems that have been studied and are
known to be in NP.
Example 14.7
The Hamiltonian Path Problem Given an undirected graph, with vertices υ 1 ,
υ 2 ,…, υ n , a Hamiltonian path is a simple path that passes through all the vertices.
The graph in Figure 14.2 has a Hamiltonian path (υ 2 , υ 1 ), (υ 1 , υ 3 ), (υ 3 , υ 5 ), (υ 5 ,
υ 4 ), (υ 4 , υ 6 ). The Hamiltonian path problem (HAMPATH) is to decide if a given
graph has a Hamiltonian path.
A deterministic algorithm is easily found, since any Hamiltonian path is a
permutation of the vertices υ 1 , υ 2 ,…, υ n . There are n! such permuations, and a
brute-force search of all of them will give the answer. Unfortunately, this comes
at a great expense, even for modest n.
To explore the nondeterministic solution, we must first find a way to