edited by
17,830 views
21 votes
21 votes

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

  1. R is NP-complete
  2. R is NP-hard
  3. Q is NP-complete
  4. Q is NP-hard
edited by

5 Answers

0 votes
0 votes
Q is Np hard from the definition ..we cannot say it np complete because we are not sure whether q belongs to np or not
Answer:

Related questions

15 votes
15 votes
7 answers
4
Kathleen asked Sep 18, 2014
11,672 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...