Question

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 of the following statements are true?
A. R is NP complete
B. R is NP Hard
C. Q is NP complete
D. Q is NP hard

Answer 1

Answer:

B. R is NP Hard

Explanation:

Given:

S is an NP complete problem

Q is not known to be in NP

R is not known to be in NP

Q is polynomial times reducible to S

S is polynomial times reducible to R  

Solution:

NP complete problem has to be in both NP and NP-hard. A problem is NP hard if all problems in NP are polynomial time reducible to it.

Option B is correct because as given in the question S is an NP complete problem and S is polynomial times reducible to R.

Option A is not correct because R is not known to be in NP

Option C is not correct because Q is also not known to be in NP

Option D is not correct because Q because no NP-complete problem is polynomial time reducible to Q.