# If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

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

## migrated from stackoverflow.comOct 13 at 9:34

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

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.