Friday, 13 March 2015

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