Thursday, June 12, 2008

Complexity Zoo Poster

There is a poster of (some of) the Complexity Zoo that was emailed to me by Ken Regan. It is on line either as a pdf file or a ppt version. (There was an earlier version a while back.)
  1. Would this poster make a good syllabus for a basic course in complexity?
  2. I prefer it NOT as a poster but as an image on line that I can zoom in and zoom out of.
  3. Is there any important complexity class that is not on the poster that should be?
  4. Is there any unimportant complexity class that is on the poster that should not be?
Posted by at

6 comments:

  1. Anonymous12:13 PM, June 12, 2008

    One item on the poster that probably shouldn't be there: "Unknown but commonly believed: L != NL". I would be surprised if the majority of people who work in log-space classes believe that they are different. There is no good evidence either way, but at least my feeling is that they collapse.

    ReplyDelete
  2. Anonymous5:04 PM, June 12, 2008

    Regarding 2., try this:

    http://test.zuiprezi.com/prezi/104/view/

    (Very rudimentary.) Zoom in/out with 1 and 2, use the arrow keys to navigate.

    Here is Greg Kuperberg's Complexity Zoo visualization in the same zoomable format:

    http://test.zuiprezi.com/prezi/103/view/

    ReplyDelete
  3. Greg Kuperberg9:23 PM, June 12, 2008

    I was going to say, my Complexity Zoology project is not just a visualization, but rather an expert system. To my knowledge, it is by far the most complete survey of inclusions and separations between decision complexity classes. I'm not sure that such a survey would be possible without expert system assistance.

    But if visualization is your interest, it is useful for that too. I don't understand the distinction between "posters" and on-line images that can be zoomed. You can zoom in most PDF previewers, and search too.

    Ken Regan's poster is very nice. Although in my opinion, the oval for BQP should not have more area than the quadrilateral for NP. The oval for BPP may also be too tall, since as the poster says, people commonly believe that P = BPP. (I would say that the derandomization arguments are extremely convincing.) Also in my opinion, MA, AM, and QMA are some other important classes.

    ReplyDelete
  4. Anonymous4:16 AM, June 13, 2008

    I was going to say, my Complexity Zoology project is not just a visualization, but rather an expert system.

    A very impressive project I didn't intend to belittle. :)

    I don't understand the distinction between "posters" and on-line images that can be zoomed. You can zoom in most PDF previewers, and search too.

    A good zooming user interface is much more suitable for these tasks than Acrobat Reader with the magnify button. Unfortunately you have to take my word for this, as my links show a pre-pre-alpha version of a good zooming interface. Still, I think it's kind of cool. I hope noone minds if I re-post the links linkified:


    Zoomable Complexity Landscape

    Zoomable Complexity Zoology

    ReplyDelete
  5. KWRegan4:13 PM, June 13, 2008

    Thanks for the comments so far. Maybe I'll ask to have a poll at Complexity on NL versus L, but my feeling of != is based substantially on the difference between random walks on directed vs. undirected graphs. Is there any indication of equality beyond Symmetric L = L (Reingold), such as progress on the non-symmetric version of RL, which is contained in NL?

    Another editorial decision was to present "nxn chess" as EXPTIME-complete. It drops into PSPACE if one suitably generalizes the "50 move rule" for the standard game. It's hard for me to tell which classification is better hinted by my concrete experience with chess, though I've been analyzing an endgame position from last year's world championship tournament of *amazing* concrete complexity.

    Mustafa Faramawi is on the Computer and Information Systems faculty at Medaille College in Buffalo, specializing in media / visual arts, and was in my graduate intro theory course in Fall 2006.

    ReplyDelete
  6. Bob Hearn2:36 PM, June 14, 2008

    I certainly wouldn't quibble with NxN Chess as EXPTIME-complete; that's one of the classic results in game complexity. But it does strike me more as an application rather than as a canonical complete problem, as most of the other labels (SAT, QBF, etc.) seem to be. For something "purer", and to fit in with problems/games on Boolean formulas, I would go with Stockmeyer & Chandra's game PEEK.

    ReplyDelete

Subscribe to: Post Comments (Atom)