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 pt)
What is the definition of P?

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

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