CISC 365 Lecture Notes - Lecture 7: Boolean Expression, Metar
21 Nov 2016
School
Department
Course
Professor
Document Summary
Example of a demonstration that a problem is np-complete by reduction from cnf-sat. Cnf- sat - we already know this, thanks to cook and levin. We need to show that cnf-sat reduces to k-clique. ) First we observe that k-clique is in np: if the answer to an instance of k- Clique is yes and we know the details of the answer, we can easily verify that the required edges are present in the graph. To show that cnf-sat reduces to k-clique, we start with an arbitrary instance of cnf-sat: a boolean expression e in cnf. Each clause of e contains some boolean variables, some of which may be negated. We will refer to these boolean variables, with or without negation, as literals. We need to construct an instance of k-clique (i. e. a graph g and an integer: in such a way that g has a k-clique i e is satis able.
