Andy's Math/CS page

Thursday, February 01, 2007

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.

Labels: ,


  • So where in CS is there a generative scheme of comparable fertility?

    It is true that complexity theory looks at the "serious" problems of tcs. But algorithms is where all the cool puzzle action is. Of the top of my head, data structures, simple number algorithms, and (computational) geometry are a rich source of cool puzzles that may or may not always be research friendly, but are always entertaining.

    Another source is probability theory, where neat paradoxes abound. You should check out some of Peter Winkler's books for some very nice puzzles that any algorithms person can appreciate.

    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?

    No, No, and No. In fact, I'd argue that the relative youth of CS is an advantage, in that simple puzzles often lead to publishable papers :). this is much less likely to happen in number theory ! For simple examples of this, look at some of the papers in SODA or SoCG over the past few years. Uri Feige's talk on Jenga was one of the most well attended talks at SODA one year, and the problem is really a cute puzzle.

    By Blogger Suresh, at 12:52 PM  

  • Many notions in theoretical cryptography, eg., zero-knowledge, secure function evaluation, public-key cryptography, have nice puzzle formulations

    By Anonymous Rahul, at 7:27 PM  

  • Thanks, Suresh! I agree that algorithms has lots of puzzle action, although I think it takes experience to tap it. Generally when I try to pose algorithmic problems to myself, they wind up being either clearly NP-hard or amenable to a small number of familiar techniques like dynamic programming--it's hard to strike at the 'fractal boundary' between P and NP. It seems like trying to improve the runtime of 'obvious' polynomial-time algorithms leads more reliably to good puzzles.

    But why shouldn't complexity theory be a richer field for puzzles than it is? At least in its efforts at showing class containments, it can often be seen as a generalized algorithmics, where instead of computing decision functions sending some set A to 1 and A's complement to 0, we try to map two disjoint sets A, B to disjoint sets C, D (this is the 'leaf language' perspective). This ought to give us a lot of freedom to define clever if useless algorithms whose discovery would make good puzzles.

    By Blogger Andy D, at 9:47 PM  

  • Rahul--agreed. For other readers, the classic crypto puzzle would have to be, How do 3 office workers compute the average of their salary without anyone revealing anything about their individual salary (and without using a computer, a trusted outside party, etc.)?

    Also see my "Puzzle Time" post which is a puzzle formulation of an oblivious-transfer result.

    Also Suresh, I have Peter Winkler's book and love it. Can't wait for the planned sequel.
    Are there academic papers on the 100-prisoners-and-a-lightbulb puzzle?

    By Blogger Andy D, at 9:53 PM  

  • So where in CS is there a generative scheme of comparable fertility?

    How about:

    * Is complexity class C in complexity class D relative to all oracles?

    * What is the query complexity (or better yet, quantum query complexity) of problem X?

    * What's the fastest algorithm for combinatorial problem Y?

    * Is property Z testable?

    * Given a family F of Diophantine equations, is it solvable by an (efficient) algorithm?

    The last scheme, in particular, would seem to imply that our generative schemes are at least as rich as the number theorists'. :-)

    By Blogger Scott, at 7:43 PM  

  • Scott--I don't dispute that there are rich schemes in TCS, only that it seems to take more insight, experience, and luck to get interesting problems out of them. "Prove C is contained in D for all oracles" requires complexity classes as inputs, and haphazardly applying the existing generative schemes for these--such as dot- and oracle- operators and for NP, BPP, PP, and so on--do not, in my experience, reliably lead to interesting classes or problems. Also, if interesting problems arise, they are less likely to have a 'puzzle' flavor--in my subjective view.

    Although, to be honest, I guess I haven't done enough of this to really say for certain. To experiment:

    is NP(BPP(NP(PP(NP(BPP))))) contained in

    BPP(PP(PP(NP))) for all oracles?

    I suppose the question is whether known relativizing inclusion results give all relativizing relations between these expressions. What do we have:

    BPP() \subseteq PP(),

    BPP(PP()) = PP(BPP()) = PP(),

    BPP(NP()) \subseteq NP(BPP()),

    PP(NP()) \subseteq NP(PP()),

    NP(NP()) = NP(), etc.

    Maybe we'll know we have a sufficiently rich vocabulary of operators when it is provably NP-hard to decide whether a containment relativizes.

    By Blogger Andy D, at 8:57 PM  

  • And once again, () is the dot operator, not oracle subroutine.

    By Blogger Andy D, at 8:58 PM  

  • I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.


    By Blogger susan, at 4:23 AM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:49 AM  

Post a Comment

<< Home