May 3, 2004

**Name:**________________________________________

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

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

- (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.