Exponential

For those following along at home, let me take a minute to explain what computer scientists mean when we talk about "linear complexity" and "exponential complexity.”

Logarithmic complexity: making pancakes. The first time, it’s a little tricky, you follow the recipe with care, some get burnt or fall apart. With practice, it gets easier. After a few years of Sunday pancakes, you can do it in your sleep. After a year of working in a breakfast kitchen, you can make pancakes for 100 while discussing Flaubert with the dishwasher. (Note, though, that even the fastest, most experienced cook takes some time to make a pancake, and two pancakes always take longer than one.)

Linear complexity: Dickens or Trollope or Stephen King embark on their next novel. It’s a lot of work, nothing in this world is certain, but they’ve done it many times before.

Quadratic complexity: You embark on your first novel, the first in what you hope to be a continuing series of mysteries set in 19th century Paris. You don’t yet know as much as you should about 19th century Paris, but your French is good and so it’s off to the library for you.

Exponential complexity: You set out to write an illustrated, rhymed epic in a dead language you don’t understand and that is unusually difficult to rhyme and for which no teachers are available, when you don’t draw or paint and you’re also wrestling with a life-threatening illness and you’re a single parent and sole support of four children, ages 1 through 14. You work at the post office to support the kids. Additional difficulties of similar magnitude will be uncovered in the course of the work.

NP-complete: it’s even harder.