[Solved] How many steps are required to prove that a decision problem is NP complete?

McqMate

Q.	How many steps are required to prove that a decision problem is NP complete?
A.	1
B.	2
C.	3
D.	4
Answer» B. 2
Explanation: first, the problem should be np. next, it should be proved that every problem in np is reducible to the problem in question in polynomial time.

787

0

Do you find this helpful?

3

View all MCQs in

Design and Analysis of Algorithms

Discussion

No comments yet

Related MCQs

Subset sum problem is an example of NP- complete problem.
How many conditions have to be met if an NP- complete problem is polynomially reducible?
The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using
Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using
You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?
What is the simplest method to prove that a graph is bipartite?
What is testing of a complete bipartite subgraph in a bipartite graph problem called?
How many spanning trees does a complete bipartite graph contain?