Let S be an NP-complete problem, 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?

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.17K Points
Coach

Q.) Let S be an NP-complete problem, 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?

(A) R is NP-complete

(B) R is NP-hard

(D) Q is NP-hard

Correct answer : Option (A) - R is NP-complete

Discusssion

Related MCQs on Theory of Computation

Q. Which protocol gives a full route table update every 30 seconds?

Q. Which of the following is not a main phase in Configuration Management (CM) Process?

Q. The 16 bit register is separated into groups of 4 bit where each groups is called:

Q. Following IC chip integrates 100 thousands electronic components per chip

Q. The type of control signal is generated based on

Q. With an IP address of 201.142.23.12, what is your default subnetmask?

Q. consider the four tsatements: 1.(p→q) ٨(p٨~q) 2.(~p→r)٨(p↔q) 3.p→(~qVr) 4.~(p٨q) V (p↔q) Which one of these four ststements is a tautology.

Q. What does xml stand for?

Q. Which one of the following is an element of directing?

Q. When a function returns a value, the entire function call can appear on the right side of the equal sign and be assigned to another variable.