Let COMPOSITE be the problem of determining whether a given integer is composite
ID: 646503 • Letter: L
Question
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.
Explanation / Answer
Composite:
Input: n-bit number, x
Output: 1 if x is a composite number; 0 otherwise.
x, is composite we `only' have to find a factor of x
Is y a factor of x?
Definition: A polynomial proof system for a decision problem D is a Boolean function f(I,c), where I is an instance of D, such that:
c is data whose encoding is of a size polynomial in that of I (i.e., if I has k bits, then c can have nk bits where k is a constant.
If f(I,c) is True for some value of c then I is in D (i.e., I is a "yes" instance of D).
f can be computed by a polynomial time algorithm.
In this definition, c is the certificate that "proves" I really is in D. A polynomial proof system is a way we can verify the result
of a decision algorithm in polynomial time.
For example, a polynomial proof system for COMPOSITE-NUMBER would go like this:
c is a positive integer.
f(I,c) returns True if c is a factor of I (i.e., divides I evenly). This can be done in polynomial time since we can do the modulus
integer arithmetic operation in time quadratic in the size of I.
So we can require suspicious algorithms for COMPOSITE-NUMBER to provide us with a certificate c that makes f(I,c) return True;
we are then satisfied that I really is composite.
Definition: NP is the class of decision problems for which there exists a polynomial time proof system.
So NP is the class of problems for which we can check proofs of "yes" instances in polynomial time. Note that P is the class of problems
for which we can find proofs in polynomial time; we can just let c be empty and use the polynomial time algorithm to yield a trivial
polynomial proof system. (NP stands for nondeterministic polynomial time, which refers to an alternate but equivalent definition that,
believe it or not, tends to give students more headaches than this one.)
Clearly, COMPOSITE-NUMBER is in NP; we just saw a polynomial proof system for it. This doesn't mean we can solve COMPOSITE-NUMBER in
polynomial time, just check proofs for it in polynomial time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.