The following question was asked on a quiz:

Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i.e., can be reduced in polynomial time) to S, and S is polynomial-time reducible to R, which one of the following statements can be deduced from the above information?

It was asked to choose a correct option out of these four options:

  1. R is NP-complete
  2. R is NP-hard
  3. Q is NP-complete
  4. Q is NP-hard

All that you know is that R is NP-hard.

To show that R is NP-complete, you need to show that it is in NP. But that is not automatically true.

As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?" These are variants of the Traveling Salesman problem. S is in NP while R is believed not to be. The issue being that given a proposed solution, you just add it up for S. But for R, there is no known polynomial way to verify that you actually have the best path.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy