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:


  
  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.