From the book, 16.2(a,b) [page 447]. Scheduling to minimize average completion time
From the book, 34.2-6 [page 1066].
Let COMPOSITE be the problem of determining whether a given integer is composite. (An integer x is composite if x > 1 and x is not prime. That is, a composite number x can be factored as x = ab, where 1 < a < x and 1 < b < x.
Show that COMPOSITE is in the class NP by choosing evidence to check and telling how to check the evidence.
One way to determine whether an integer x > 2 is composite is to test each number from 2 to x−1. If one of those numbers is a factor of x, then you conclude that x is composite. Otherwise, you conclude that x is prime.
Is that a polynomial time algorithm for COMPOSITE? Be sure to remember that a polynomial time algorithm must take time O(nk) where k is fixed and n is the length of the input.