Example problems with polynomial and exponential solutions, and tiny footprint? I'm planning on running an “experiment” when teaching my algorithms class this fall, with one very old, limited computer (main limiting factor is probably memory—possibly as low as 16KB) and one modern/standard one. The idea being to solve a problem with a polynomial one, running on the slow computer, and an exponential one on the fast one (and, of course, have the slow one win).

The problem is finding a suitable problem—one where the running times will be really different for instances of very limited size (and, preferably, where the data structures are quite simple; the primitive computer is … primitive). I originally thought about sorting algorithms (e.g., quadratic vs. linear), but that would require far too large instances (unless I went with bogosort, for example).

At the moment, the only (rather boring) example I've thought of is computing Fibonacci numbers the smart and the stupid way. It would be nice to have something a little less tired/overused, and preferably something (semi-)obviously useful. Any ideas/suggestions?
You could do regular expression matching. A naive backtracking matcher can easily be pushed into exponential behavior on inputs that a smarter matcher can handle in linear time.