Mark Dominus collected a few examples of polynomial-time reductions from “regular expression” matching to NP-hard problems. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?

Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?