To visit fifty cities in the most efficient way,
To pack the greatest value in a crate,
To finish all the tasks that are assigned to you today.
So that none of them start early or end late.
To partition fifty integers to sets with equal sums,
To pack fifty bins with all of your possessions.
To choose fifty people so that every two are chums.
To satisfy some Boolean expressions.
These tasks and thousands more are fundamentally the same.
An exponential running time has never yet been beat.
In computation theory, they bear a famous name:
They're Non-deterministic Polynomial-time Complete.
The theory here is Levin's, Richard Karp's and Stephen Cook's.
If you prove they're hard or easy, you will get a million bucks!
This is part of the collection Verses for the Information Age by Ernest Davis