COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
1
|
|
|
2
|
|
|
3
|
|
|
4
|
Detailed explanation-1: -To prove a problem NP Complete, there are two steps involved: Prove given problem belong to NP Class. All other problems in the NP class can be polynomial time reducible to that problem.
Detailed explanation-2: -We can solve Y in polynomial time: reduce it to X. Therefore, every problem in NP has a polytime algorithm and P = NP. then X is NP-complete. In other words, we can prove a new problem is NP-complete by reducing some other NP-complete problem to it.
Detailed explanation-3: -In order to prove that a problem L is NP-complete, we need to do the following steps: Prove your problem L belongs to NP (that is that given a solution you can verify it in polynomial time) Select a known NP-complete problem L’
Detailed explanation-4: -To prove VC is NP, find a verifier which is a subset of vertices which is VC and that can be verified in polynomial time. For a graph of n vertices it can be proved in O(n2). Thus, VC is NP. Now consider the “clique” problem which is NPC and reduce it into VC to prove NPC.
Detailed explanation-5: -For a decision problem A to be in NP, it is sufficient to show that a certificate (an encoding of a solution to the problem) can be verified to represent a solution to the decision problem in polynomial time.