Name:________________________________________

1. (2 pts) How do you show that a language L is NP-complete, using the reduction method?
   
   
   
   
   
   
   
   
2. (1 pt) Humpty-Dumpty recalls that 3-SAT (the set of all satisfiable boolean formulas in conjunctive normal form with 3 literals per clause) is a subset of SAT (the set of all satisfiable bolean formulas in conjunctive normal form) and both are NP-complete. He conjectures that any language that is a subset of an NP-complete language is also NP-complete. Is his conjecture true or false?
   
   
   
   
   
   
3. (2 pts) What is the definition of an approximation algorithm for an NP-complete problem with ratio bound K?