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.

Published by Mr. Dubey ⭐ 104.82K Points at 16-Sep-2023 03:44 pm in Design and Analysis of Algorithms

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

Related MCQs

Q. Which phase is not available in software life cycle?

Q. What does the virtual machine software layer do?

Q. The principal parameters that determine the communication latency are as follows:

Q. Longest palindromic subsequence is an example of

Q. Select which clause in OpenMP is similar to the private, except values of variables are initialized to corresponding values before the

Q. The right hand side of an association rule is called__________.

Q. If S=1 and R=0, then Q(t+1) = for positive edge triggered flip-flop

Q. In tag data can be changed over time.

Q. A command to remove a relation from an SQL database

Q. Which of the following are character special files?

📊 Question Analytics

👁️
942
Total Visits
📽️
3 y ago
Published
🎖️
Mr. Dubey
Publisher
📈
85%
Success Rate