Wilf, page 107, line 13, says: "Any suggestions for a certificate?"
Here's a suggestion: List all possible tours, and next to each, write its total length. This can be done algorithmically. This is my "certificate". Verifying the certificate is easy: add up the distances for each tour, and check that the total given for each tour in the list is correct; then check that none of these totals is less than K. Is there anything wrong with my certificate? Did I prove that the problem "There is no tour of length less than K" is in NP?
In Problem 1 on p.109, suppose we find an algorithm that solves the problem using a polynomial number, P1(n), of pairwise comparisons between the integers, where n is the number of integers given. Suppose each integer in the input has at most d digits (in binary). Suppose each comparison takes at most a polynomial number, P2(d), of steps. Let’s define input size I as the sum of number of digits in all the n integers. We’d like to show this algorithm is “fast”. Better yet, prove the following lemma, which is a generalization of the above.
Lemma: Suppose for a given decision problem the input consists of a set S with n elements. Suppose there is an algorithm that solves the problem using P1(n) operations, and each operation takes at most P2(d) steps, where each element of S has size at most d. If P1 and P2 are polynomial functions, and if input size is defined as the total size of all the elements in S, then the given algorithm is “fast”.
You may assume P1 and P2 are non-decreasing. (If you find this lemma too abstract, first just do the version stated before the lemma; and then do the lemma.)