Slide 1MenuProblem Classes if P  NP:Problem Classes if P = NP:The 3SAT Problem3SAT Example3SAT  SmileyNP CompleteSlide 9Quiz AnswersQuiz Responses: What is Computer Science?Slide 12Slide 13Computer ScienceWhere we’ve been, Where we’re goingComputer Science: CS150 so farCS150 upcomingFamous Computer ScientistsSlide 19NP Complete ProblemsNP-Complete ProblemsTraveling Salesperson ProblemGraph (Map) Coloring ProblemMinesweeper Consistency ProblemPegboard ProblemSlide 26Drug Discovery ProblemIs it ever useful to be confident that a problem is hard?ChargeDavid Evanshttp://www.cs.virginia.edu/evansClass 16: NP-Completeness /The Story so FarCS150: Computer ScienceUniversity of VirginiaComputer Science2CS150 Fall 2005: Lecture 16: NP CompletenessMenu•3SAT•Complexity class NP-Complete•The Story so Far•Some NP-Complete Problems3CS150 Fall 2005: Lecture 16: NP CompletenessProblem Classes if P  NP:PNPSorting: (n log n)Simulating Universe: O(n3)Smileys: O(n!) and (n) Find Best: (n)(n)How many problemsare in the (n) class?How many problemsare in P but not in the (n) class?How many problemsare in NP but not in P?infiniteinfiniteinfinite4CS150 Fall 2005: Lecture 16: NP CompletenessProblem Classes if P = NP:PSorting: (n log n)Simulating Universe: O(n3)Smileys: (nk)Find Best: (n)(n)How many problemsare in the (n) class?How many problemsare in P but not in the (n) class?How many problemsare in NP but not in P?infinite0infinite5CS150 Fall 2005: Lecture 16: NP CompletenessThe 3SAT Problem•Input: a sentence in propositional grammar, where each clause is a disjunction of 3 names which may be negated.•Output: Either a mapping from names to values that satisfies the input sentence or no way (meaning there is no possible assignment that satisfies the input sentence)6CS150 Fall 2005: Lecture 16: NP Completeness3SAT Example3SAT ( (a  b   c)  (a   b  d)  (a  b   d)  (b   c  d ) ) { a: true, b: false, c: false, d: false}Sentence ::= ClauseClause ::= Clause1  Clause2 (or)Clause ::= Clause1  Clause2 (and)Clause ::= Clause (not)Clause ::= ( Clause )Clause ::= Name7CS150 Fall 2005: Lecture 16: NP Completeness3SAT  Smiley•Like 3/stone/apple/tower puzzle, we can convert every 3SAT problem into a Smiley Puzzle problem!•Transformation is more complicated, but still polynomial time.•So, if we have a fast (P) solution to Smiley Puzzle, we have a fast solution to 3SAT also!8CS150 Fall 2005: Lecture 16: NP CompletenessNP Complete•Cook and Levin proved that 3SAT was NP-Complete (1971) (Take CS660 to see how)•A problem is NP-complete if it is as hard as the hardest problem in NP•If 3SAT can be transformed into a different problem in polynomial time, than that problem must also be NP-complete.•Either all NP-complete problems are tractable (in P) or none of them are!9CS150 Fall 2005: Lecture 16: NP CompletenessProblem Classes if P  NP:PSorting: (n log n)Simulating Universe: O(n3)SmileysFind Best: (n)(n)How many problemsare in the (n) class?How many problemsare in P but not in the (n) class?How many problemsare in NP but not in P?infiniteinfiniteinfiniteNP3SATNP-CompleteNote the NP-Complete class is a ring – others are circles10CS150 Fall 2005: Lecture 16: NP CompletenessQuiz Answers•What would we need to do to prove a problem is O (n4)? •What would we need to do to prove a problem is Ω (n4)? Find a procedure that solves the problem that is Ο(n4).Prove that there is no procedure that solves the problem that is faster than (n4).11CS150 Fall 2005: Lecture 16: NP CompletenessQuiz Responses: What is Computer Science?Remembered (or almost remembered first class): Study of "how to" knowledge, or whatever the fancy name for that is, The imperative study of procedures and language (I'm trying to remember what that definition was on the first day), "How to" do things; instead of declarative statements, talk about how to do things, I know we hade a specific definition in the beginning of the year but I forget it…I would say that computer science is a science/study of methods of manipulating data and information, the study of imperative knowledge; It doesn't need to have a computer and it's not a science, it doesn't deal with real things, instead numbers and data manipulations and problem solving; a liberal art, an innovative perspective on information; Study of imperative knowledge. Study of different types of problems and how to solve them. It's more of a liberal arts major than engineering.; liberal art! Learning about languages.; CS is not computer engineering, and its not science. Nevertheless, CS used sciences to prove computer problems.12CS150 Fall 2005: Lecture 16: NP CompletenessQuiz Responses: What is Computer Science?Problem solving (logic, language): A way of thinking about computers and programs. A systematic way of creating and understanding how programs work, thinking differently, logically to how the computer language functions, It seems to be to theorize on how to systematically solve problems in a functional language, the study of logic and programs that can be understood by computers; Study of logics and way to solve problems; The study of using systems and algorithms to solve problems.; study of languages used to create intelligent computer procedures to solve usually huge or complex problems involving data ?!; the science of computers? Solving problems with computers; The study and use of languages to improve technology and program computers; CS is the art of getting a computer to do what you want through a common language.13CS150 Fall 2005: Lecture 16: NP CompletenessQuiz Responses: What is Computer Science?Amusing: Computer Science is a great way to find new world.The bane of my existence.14CS150 Fall 2005: Lecture 16: NP CompletenessComputer Science•(Expanded) Definition from Class 1:–Study of information processes•How to describe information processes by defining procedures•How to predict properties about information processes•How to elegantly and efficiently implement information processes in hardware and softwareWhat have we spent most of our time on so far?15CS150 Fall 2005: Lecture 16: NP CompletenessWhere we’ve been, Where we’re going16CS150 Fall 2005: Lecture 16: NP CompletenessComputer Science: CS150 so far•How to describe information processes by defining procedures–Programming with procedures, lists,