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