CPSC 411: Quiz 10
November 6, 2008

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

Signature:___________________________________________

P, NP, and NP-complete are classes of problems. Give the definitions below.

  1. (1 pt) What is the definition of P?





  2. (2 pts) What is the definition of NP?







  3. (2 pts) What is the definition of NP-complete?