This website is primarily, in effect, a front end to Scott Aaronson's Complexity Zoo. That is a great wiki, and credit is due first to everyone working on that.
The overal goal of this page/site are to organize that information in a formal way -- something that precise enough that it could, in principle, be fed into an automated reasoning system and formally verified. But that is not the purpose. The actual objectives are a few:

• A structured data format (JSON) that could be more easily adapted to other uses/displays. This includes, for instance, automatic "chaining" of theorems to give succinct explanations, or making the hierarchy diagram.
• Slightly more precise/formal distinctions between classes, in particular drawing distinctions between:
  • languages
  • promise problems
  • function problems
  • sampling problems
  • and all of their parameterized variants.
  Often these are disregarded Issues arise when e.g. people talk about "QMA-complete" problems, which are very natural to talk about, while at same time people regularly mention the conjecture that there are no BPP-complete problems. The are natural PromiseBPP-complete problems, and natural PromiseQMA-complete problems. The issue is just that when people say "QMA" they always imply the "promise".
• Slightly more precise handling of uniform/nonuniform classes. Quantum classes are almost all technically "circuit" classes, but uniformity is understood (typically L-uniformity). Cryptographers talk about circuit classes and typically assume no uniformity. But important containments like "NC¹ is in L" only make sense if there is uniformity. To make things formal, this must be rectified.

There is one more objective here, which is to help me learn more about complexity theory myself. :)

--Alex Meiburg


If you want to contact me, click to show, or post an issue at the GitHub repo