Java Reference
In-Depth Information
many approaches to finding an acceptable solution to this particular NP-complete
problem in a reasonable amount of time.
For more information about the Collatz function see “On the Ups and Downs
of Hailstone Numbers” by B. Hayes [Hay84], and “The 3x + 1 Problem and its
Generalizations” by J.C. Lagarias [Lag85].
For an introduction to the field of computability and impossible problems, see
Discrete Structures, Logic, and Computability by James L. Hein [Hei09].
17.5
Exercises
17.1 Consider this algorithm for finding the maximum element in an array: First
sort the array and then select the last (maximum) element. What (if anything)
does this reduction tell us about the upper and lower bounds to the problem
of finding the maximum element in a sequence?
Why can we not reduce
SORTING to finding the maximum element?
17.2 Use a reduction to prove that squaring an nn matrix is just as expensive
(asymptotically) as multiplying two nn matrices.
17.3 Use a reduction to prove that multiplying two upper triangular nn matri-
ces is just as expensive (asymptotically) as multiplying two arbitrary nn
matrices.
17.4 (a) Explain why computing the factorial of n by multiplying all values
from 1 to n together is an exponential time algorithm.
(b) Explain why computing an approximation to the factorial of n by mak-
ing use of Stirling's formula (see Section 2.2) is a polynomial time
algorithm.
17.5 Consider this algorithm for solving the K-CLIQUE problem. First, generate
all subsets of the vertices containing exactly k vertices. There are O(n k ) such
subsets altogether. Then, check whether any subgraphs induced by these
subsets is complete. If this algorithm ran in polynomial time, what would
be its significance? Why is this not a polynomial-time algorithm for the K-
CLIQUE problem?
17.6 Write the 3 SAT expression obtained from the reduction of SAT to 3 SAT
described in Section 17.2.1 for the expression
(a + b + c + d) (d) (b + c) (a + b) (a + c) (b):
Is this expression satisfiable?
17.7 Draw the graph obtained by the reduction of SAT to the K-CLIQUE problem
given in Section 17.2.1 for the expression
(a + b + c) (a + b + c) (a + b + c) (a + b + c):
Is this expression satisfiable?
 
Search WWH ::




Custom Search