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? R is NP-complete R is NP-hard Q is NP-complete Q is NP-hard Algorithms gatecse-2006 algorithms p-np-npc-nph normal isrodec2017 out-of-gate-syllabus + – Rucha Shelke asked Sep 17, 2014 edited Dec 19, 2017 by Arjun Rucha Shelke 17.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Bhagirathi answered Sep 18, 2014 Bhagirathi comment Share Follow See all 0 reply Please log in or register to add a comment.