M

Mr. Dubey • 52.30K Points
Coach 

Q. How many conditions have to be met if an NP- complete problem is polynomially reducible?

(A) 1
(B) 2
(C) 3
(D) 4
Correct : Option (B)

Explanation: 
 a function t that maps all yes instances of decision problems d1 and d2 and t should be computed in polynomial time are the two conditions.

Share

Discusssion

Login to discuss.

Be the first to start discuss.

Related MCQs

Q. AT T0 THE VALUE STORED IN A 4-BIT LEFT SHIFT WAS “1”. WHAT WILL BE THE VALUE OF REGISTER AFTER THREE CLOCK PULSES?

Q. What Is Constant? A Constants Have Fixed Values That Do Not Change During The Execution Of

Q. Array with last element 'n' will always have array size equal to _______.

Q. Which structure can be modelled by using Bipartite graph?

Q. The data field cannot carry which of the following?

Q. What is the extension for a Visual Basic web form interface file?

Q. ————- pattern splits system into a number of computationally independent execution structures to achieve optimized usage of re

Q. The dual of the scatter operation is the

Q. Which testing cannot be performed on first build of the software?

Q. How many verb tenses are there in the English language?