[Overview] [Previous]
[Next]

# Additional NP Problems

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 M_{1}, M_{2}, M_{3}, ..., M_{n},
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.

Copyright © 1996 by David Matuszek

Last modified Apr 23, 1996