Complexity Class of the Week

When I was at U. Chicago, we would have a semiregular feature call the Complexity Class of the Week where we would pick a complexity class or other concept and on a white board in the lounge write the definition, what was known, how it related to other classes and perhaps most importantly what open questions remained.

I decided to revive this tradition here on this virtual whiteboard in the ultimate lounge known as the internet.

Scott Aaronson has set up a Complexity Zoo that gives a short description of many classes that make a good reference. We will go more in depth for a single class or concept but Aaronson's site makes for a good reference for other classes we mention.

Watch this space tomorrow for the first complexity class of the week. Feel free to email me with suggestion for future classes of the week, especially if you are willing to contribute a write-up.