Scheduling finals without the headache

This Tech Talk column originally appeared in The Exponent (University of Alabama in Huntsville), Vol. 32, No. 16 (January 18, 2001) and was later reprinted on February 7, 2002. Digitized issue: UAH LOUIS archive. Reproduced here courtesy of that archive.

Want to become rich and famous while helping people out at the same time?

If you’ve been around UAH for more than a couple of semesters, then you’re probably aware of the University’s policy that no student must suffer the indignity of taking more than two finals on the same day. The policy is great until someone tries to invoke it, because it’s up to students to secure their instructors’ permission to reschedule finals. “Great,” our fearless hero thinks, “now I can delay that final I was dreading because I hated the material, the teacher was boring, and I hardly ever went,” so he asks about rescheduling the final. Anyone who has been in that situation can predict the response: “Did you talk to the other instructors yet?” I never had the luxury of being the guy in the E*Trade commercial who got room, board, and spending money in exchange for rubbing some rich old lady’s bunions, so I had to go see professors on my lunch break or some other time that I could get away from work. Instructors are hard enough to catch as it is, so three in the same day near finals pretty much requires a miracle.

With all the Ph.D.s in the employ of the University, surely someone is clever enough to come up with a finals schedule such that no one would have more than two finals on the same day and thus spare everyone the headache of chasing down instructors. If that were true, then scheduling finals would quickly become a former UAH employee’s problem—because whoever solved it would be rich and famous.

Computer scientists and mathematicians call problems like this NP-complete. Informally, it’s easy to verify potential solutions to NP-complete problems, but no one knows of a fast way to construct a correct solution. NP-complete problems also have the interesting property that if you find a fast way to solve one, that fast solution can be applied to yield a fast solution to all other NP-complete problems! In other words, people all over the world who have been grappling with excruciatingly difficult problems would want to use your solution. To put it in terms of economics, there would be near-infinite demand, and you’d control the supply. If you still don’t get it: think “ka-ching!”

If the exam scheduling problem seems too hard, there are plenty of other NP-complete problems. For example, say you work for the FCC, and you’re in charge of assigning frequencies to FM stations. Given that there are only so many stations on the dial, can you assign a frequency to every station in the country without having two stations with overlapping listening areas transmitting on the same frequency? (Computer geeks call this the graph-coloring problem.) Here’s another: say you’re in a cave where you’ve found a bunch of treasure. You have a knapsack, but it can only hold so much weight. Can you load your knapsack with treasures that are worth at least $10 million but are under your knapsack’s weight limit? (This problem’s name is unoriginal: the knapsack problem.)

There is a downside to all of this. NP-completeness is the veil of secrecy offered by digital encryption, e.g., the Secure Sockets Layer technology that web browsers use to protect your credit card from peering eyes. Applied Cryptography is worth your while.