Design and Analysis of Algorithms20805 marksNP Complete Problems, NP Completeness and Reducibility, Cook
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete".
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete". [5]
A problem X is called NP-complete if it satisfies both of the following conditions: 1. X belongs to NP: The problem X can be verified in polynomial time. That is, given a candidate solution (certificate), we can check whether it is correct in polynomial time. 2. X is NP-hard: Every other problem ...