Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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:
- R is NP-complete
- R is NP-hard
- Q is NP-complete
- 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.
