CPSC 311, Sec 501: Quiz 11
Apr 23, 2004

Name:________________________________________

  1. (1 pt) What is the class P?





  2. (1 pt) What is the class NP?





  3. (1 pt) What is the relationship between P and NP?





  4. (2 pts) What is the definition of a language being NP-complete?