Eventually, every father has to deal with the question, “How does Santa deliver all his presents in one night?” And every father has a different answer. I don’t really remember what my dad told me—probably that Santa was really fast, or something. But I think that answer is entirely too simple; clever kids will undoubtedly see through that. So I’m not going to give my kids that explanation.

Instead, I’m going to tell them that Santa is nondeterministic: on Christmas Eve night, he actually splits into a number of parallel Santas that proceed to deliver gifts to little children; obviously, there is a one-to-one mapping of Santas to houses. At the end of the night, the Santas compare notes and verify that each house received a visit. (Assuming there are n houses, this verification step can be completed in polynomial time.)

As long as my kids don’t ask me to prove that gifts can be delivered to houses in polynomial time, I should be golden.