Where Are The Puzzles?

I am not a number theorist--far from it. It's not just that I suspect I wouldn't be very good (though there's that): while I admire its beauty, depth, and growing applicability, on a basic level I don't 'buy in' to the scenarios it presents--they don't seem real and urgent in the way theoretical CS problems do (and I say this despite being almost equally far in my tastes from 'applied' math).

But I don't want to rag on number theory, or give a polemic in favor of my field. I want to point out a sense in which number theorists seem to have it really, really good, and ask whether TCS people could ever work themselves into a similar position.

Number theorists live in a towering palace of puzzles. I don't think any other branch of math, not even Euclidean geometry, has produced such a wealth of problems. A meaningful diversity, too, in terms of range of difficulty, types of thinking and visualization involved, degree of importance/frivolity, etc. This has several benefits to the field:

i) supports more researchers, and researchers of varying abilities and approaches;

ii) gives researchers ways to blow off steam or build their confidence before tackling 'serious' or technical problems in number theory;

iii) provides more 'sparks' for theoretical development and conceptual connections;

iv) gives young mathematicians plenty of opportunities to cut their teeth (the Olympiad system seems to produce 18-year-old number theorists of demoniacal skill);

v) provides good ways to advertise the field to the public and entice in new young talent.

Feel free to chime in with other possible benefits--or maybe you think puzzles are a detriment (I've heard this expressed); if so I'd also love to hear from you.


I'm not anxious to hammer down what a puzzle is, or the exact role they play in scientific fields (others have tried); but I would like to get a better sense, in the specific case of TCS, of where the puzzles are or why they are fewer in number (I'm not saying there are none). Towards that end I'd like to first point out what may be a salient feature in number theory's success: it possesses at least one powerful generative syntax for puzzle-posing: namely

Find solutions to F(x, y, z, ...) = 0,

where x, y, z are integral and F is a polynomial, exponential function, etc. You can just start inventing small equations, and before too long you'll come across one whose solution set is not at all obviously describable, and worth puzzling over.

Now, complexity theorists have a pat explanation why this is so: solving Diophantine equations is in general undecidable, maybe even hard on average under natural distributions (?). But, though amazing and true, I think it's a sham explanation. Diophantine equations somehow manage to be (for number theorists at least) interesting on average, meaningful on average, and actually pertinent to the life of the field. (number theorists--am I wrong?)

So where in CS is there a generative scheme of comparable fertility? Are there inherent reasons why CS as we know it could not support such a scheme? Is CS too 'technical', too 'conceptual' to support that kind of free play? Or is it simply too young a field to have yielded up its riches? What do readers think?


I don't want to suggest that there aren't good puzzles and puzzle-schemas kicking around CS (contests, too, though weighted towards programming); there was a period when "prove X is NP-complete" was virtually my mission statement (though it gets old, I gotta say... and we should also admit that some of the best puzzles in any field are likely to be ones that don't fit any familiar scheme). You should also check out the impressive efforts of Stanford grad student Willy Wu, who has a cool collection of riddles, many about CS, and a long-running forum devoted to posing, solving, and discussing them.