01:198:344 Lecture Notes - Lecture 17: Vertex Cover, Boolean Satisfiability Problem, Hamiltonian Path
30 Nov 2017
School
Department
Course
Professor
Document Summary
This lecture: poly time reductions: polytime reduction: given an instance of problem a of size n, convert it in polynomial time p(n) to an instance of problem b. If b is solvable in poly time q(n) for input size n, then this means a can be solved in time q(p(n)) which is still poly time. If a is hard (say takes more than a poly time or we don"t know of a poly time algorithm and suspect it takes longer), then b is hard as well (in that sense). A 3cnf formula is the and of clauses each of which is or of 3 literals (boolean variables xi or its negation xi). Example is (a b c) ( a c d) or simply (a . A 3cnf is satis ed if there is an assignment of t/f to variables xi that make the formula evaluate to true (t). For example, a = t, d = t satis es the example.
