CISC 365 Lecture Notes - Lecture 8: C Max, Message Passing, While Loop
21 Nov 2016
School
Department
Course
Professor
Document Summary
Fortunately, most of the reductions that we do in practice are far less arduous than the cnf-sat to k-clique reduction. For most new problems we are likely to encounter, the odds are very high that someone has already proved that a similar problem is np-complete. Reductions between similar problems are usually pre y straightforward. There are some well-established techniques for creating reductions - we will look at a couple here. We have already de ned these two problems: Both of these are obviously decision problems, and both are clearly in np (situation check - make sure you understand the di erence between saying a problem is in np, and saying the problem is np-complete. Let"s suppose for the moment that we know that partition is np-complete (it is), and see how we could use that knowledge to prove that subset sum is np- complete.
