CPSC 211, Sec 201-203: Quiz 12
May 3, 2004

Name:________________________________________

  1. (1 pt) What is the definition of the time complexity of a problem (as opposed to that for an algorithm)?







  2. (2 pts) What is the real-world impact of discovering that a particular problem is NP-complete?







  3. (2 pts) True or False: There exists an algorithm to determine whether or not an arbitrary program halts (does not go into an infinite loop) on an arbitrary input.