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

M

Mr. Dubey

🎓 Coach ⭐ 103.80K Points

📊 Design and Analysis of Algorithms

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

(A) 1
(B) 2
(C) 3
(D) 4

💬 Discuss

✅ Correct Answer: (B) 2

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.

Explanation by: Mr. Dubey

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.

💬 Discussion

📊 Question Analytics

👁️

930

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

91%

Success Rate