Week 10 additional tutorial problem

Make sure you've solved discussion manual problem 15.4 first. 

 

Define the "Peak Existence" problem as follows: given an array of distinct real numbers, does the array have a peak? For example on the input A=[−1, 3, 6, 7, 0] the answer is "yes", and on the input A=[−1, 3, 2, 7, 0], the answer is "no".

 

1) Explain why the Peak Existence problem is in NP and also in co-NP.

2) Suppose for now that it were known that the Peak Existence problem is NP-complete. Can you determine whether there exists a polynomial-time algorithm for determining whether a graph has a Hamiltonian Cycle, i.e. a cycle that uses every vertex of the graph? (Hint: Don't try to actually develop such an algorithm. Instead, first argue that the Peak Existence problem is in P and the Hamiltonian Cycle problem is in NP, and then use our defintion of NP-complete.)

3) Based on what is currently known, how likely is it that Peak Existence is actually NP-complete - certain, likely, unlikely, or impossible?