Java Reference
In-Depth Information
(c) What does it say about the question of P = NP if the conditions
described in this problem existed?
17.13 Here is another version of the knapsack problem, which we will call EXACT
KNAPSACK. Given a set of items each with given integer size, and a knap-
sack of size integer k, is there a subset of the items which fits exactly within
the knapsack?
Assuming that EXACT KNAPSACK is NP-complete, use a reduction argu-
ment to prove that KNAPSACK is NP-complete.
17.14 The last paragraph of Section 17.2.3 discusses a strategy for developing a
solution to a new problem by alternating between finding a polynomial time
solution and proving the problem NP-complete. Refine the “algorithm for
designing algorithms” from Section 15.1 to incorporate identifying and deal-
ing with NP-complete problems.
17.15 Prove that the set of real numbers is uncountable. Use a proof similar to the
proof in Section 17.3.1 that the set of integer functions is uncountable.
17.16 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining if an arbitrary program will print any output is un-
solvable.
17.17 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining if an arbitrary program executes a particular state-
ment within that program is unsolvable.
17.18 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining if two arbitrary programs halt on exactly the same
inputs is unsolvable.
17.19 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining whether there is some input on which two arbitrary
programs will both halt is unsolvable.
17.20 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining whether an arbitrary program halts on all inputs is
unsolvable.
17.21 Prove, using a reduction argument such as given in Section 17.3.2, that the
problem of determining whether an arbitrary program computes a specified
function is unsolvable.
17.22 Consider a program named COMP that takes two strings as input. It returns
TRUE if the strings are the same. It returns FALSE if the strings are different.
Why doesn't the argument that we used to prove that a program to solve the
halting problem does not exist work to prove that COMP does not exist?
17.6
Projects
17.1 Implement VERTEX COVER; that is, given graph G and integer k, answer
the question of whether or not there is a vertex cover of size k or less. Begin
Search WWH ::




Custom Search