Complexity Classes Map

By Bobby on Tue, 30 Dec 2008 08:09:01 +0000

: complexity class, map, graphviz, complexity zoo,

After scanning the Complexity Zoo, extracting contains, is-contained and equals relationships between complexity classes and graphing them (using the somewhat buggy GraphViz) this is what i ended up with:
http://legacy.bloo.us/temp/zoograph2.png

There's certainly alot of information missing (and perhaps a few incorrect edges and nodes) - the scanner couldn't understand everything - but it does show one thing: if we had all the complexity class data in a queryable format (XML or database) alot of interesting (and useful) stuff could be done.

In the graph, a directed edge from A to B means A is (not necessarily strictly) contained in B. Many of these edges are open questions (is the containment strict or are they equal?). In such scenarios additional edges can be added if we assume that A = B or that A is strictly contained in B, and so on. Having this data in a queryable format might allow us to run queries that tell us how the graph will change given different assumptions, which is already challenging to compute manually as there are almost 500 classes.
Creative Commons License The Complexity Classes Map article by Bobby Soares, unless otherwise expressly stated, is licensed under a Attribution-Noncommercial-Share Alike 3.0 United States License.


Comment moderation is on, so your comments may not be visible immediately after posting.



(see all) web service, tile engine, google docs, flash, window, penn, pixel, python, game, compiler, server, tlslite, token, reference, rtmp, vmware, p vs np, Google Docs, poweredge, javascript, component, vbulletin, proxy, networking, vmware esxi, GData, forum, plugin, gwt, outlook, scales, puzzle, GWT, java, attach, shining force, subsets, appengine, permutations, pong, authentication, roland, screenshot, np-complete, gdata, neural net, php, latex, audio, AppEngine