Week 10 additional tutorial problem

Make sure you've solved discussion manual problem 15.4 first. Define the "Peak Checking" problem as follows: given A and i, where A is a (one-indexed) array of distinct real numbers which is already known to have a peak, and i is an index into A, is the peak of A at index i or not? For example on the inputs A=[−1, 3, 6, 7, 0] and i=4, the answer is "yes", and on the inputs A=[−1, 3, 6, 7, 0] and and i=2, the answer is "no".

 

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

2) Suppose for now that it were known that the Peak Checking 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 Hamiltonian Cycle problem is in NP, and then use the defintion of NP-complete.)

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