[Overview] [Previous] [Next]
The following problems all have a polynomial-time solution on a nondeterministic machine, but an exponential-time solution on a deterministic machine. There are literally hundreds of additional examples.
A salesman, starting in Harrisburg, wants to visit every capital city in the 48 continental United States, returning to Harrisburg as his last stop. In what order should he visit the capital cities so as to minimize the total distance travelled?
Every capital city has direct air flights to at least some other capital cities. Our intrepid salesman wants to visit all 48 capitals, and return to his starting point, taking only direct air flights. Can he find a path that lets him do this?
Do two distinct regular expressions represent the same language?
Given a set of finite automata M1, M2, M3, ..., Mn, all over the same alphabet A, is there some string in A* that is accepted by all of these automata?
You have on hand X amount of butter, Y amount of flour, Z eggs, etc. You have cookie recipies that use varying amounts of these ingredients. Different kinds of cookies bring different prices. What mix of cookies should you make in order to maximize profits?
This type of problem is sufficiently important that entire college courses are devoted to it, usually in the College of Business.
Copyright © 1996 by David Matuszek
Last modified Apr 23, 1996