1
$\begingroup$

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
$\endgroup$

migrated from stackoverflow.com Oct 13 at 9:34

This question came from our site for professional and enthusiast programmers.

2
$\begingroup$

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.

$\endgroup$

Your Answer

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