Question 2.
Suppose a known problem X with unknown complexity. We know that we can verify a given instance of X in polynomial time. Suppose, also, that it is able to reduce a known NP-complete problem to X in polynomial time. If, after some research, we were to discover that there is a polynomial time algorithm that solves problem X, then...
A) X, which is NP-hard, proves that P == NP.
B) X, which is NP-hard, proves that P != NP.
C) X, which is NP-complete, proves that P == NP.
D) X, which is NP-complete, proves that P != NP.
E) None of the above.
No comments:
Post a Comment