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

## The travelling salesman problem

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?

## The Hamiltonian circuit problem

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?

## Equivalence of regular expressions

Do two distinct regular expressions represent the same language?

## Intersection of finite automata

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?

## Linear programming

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.