Evan Alba

Complexity Cosmos

I was always curious about the unsolved and mysteries in the world. Through my time in university, while I was surfing through the world wide web, I stumbled on a Wikipedia page about the unsolved problems in computer science. Especially, one of the unsolved problems that caught my eye was the famous computer science P versus NP problem. A problem which questions the power limitations computers can have in solving problems. After doing some research around the P versus NP problem, I stumbled around these abstract symbols I had no clue about but it looked interesting such as: \[ {\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})} \] After that, I never really looked into deeper into the whole P versus NP problem was about. Until one day, in one of my university courses during my semester in Spring 2024, in my CSCI 411 - Advanced Algorithms and Complexity course, the professor briefly mentioned the famous unsolved P versus NP problem in some lecture. As well our professor shared a YouTube video in lecture about the P versus NP problem. While in that YouTube video, it mentioned besides there being P and NP classes of problems, there was other classes of problems that caught my interest. It caught my interest due to being related to the P versus NP problem and also gave me feelings of being an explorer out there in mysterious universe trying to discover the different types of planets and galaxies. Where the planets to me where like the different type of problems classes out there and my spacecraft was a computer. I also thought of myself of being like James T. Kirk in the tv show called Star Trek trying to explore these strange new worlds of classes of problems. Where James T. Kirk mentions in the introduction of every Star Trek episode saying, "Space, the final frontier. These are the voyages of the starship Enterprise. Its 5-year mission: to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no man has gone before." Next, after I was done attending my lectures for the day, I researched a bit and discovered the computer science field that studied these different types of problems classes was called computational complexity theory. Having no experience and no clue how I would take on the big challenge of studying computational complexity theory, especially it being a heavy mathematical field with my small knowledge of mathematics, and other life responbilities like my university courses, I just took a break off of trying to self study computational complexity theory. Until by the end of my fall semester 2024 and I was off for winter break, I took it upon myself and own interests to try to learn computational complexity theory. Finally, one of my goals while self-studying computational complexity was to create an interactive map on this website illustrating the inclusion relationships between some complexity classes that hold relative to all oracles. Note: More classes may be added in the future. You can interact with the map below. Complexity class inclusion refers to the relationship between two complexity classes where all problems belonging to one class are also considered to be in the other class, meaning that any problem solvable within the smaller class can also be solved within the larger class, typically based on the idea that the larger class allows for more computational resources like time or space. Credits given and inspiration from Complexity Zoo, Complexity Zoology, "Complexity Zoology" by Robert Joseph Sanders, Jr., and Paperscape. Note: Refer to Combinatory Complexity: Operators on Complexity Classes for the operators being used here. Let A and B be complexity classes, relativized by an oracle X.

How to interact with the diagram:

Click on a node to compare it to other complexity classes. Clicking a node marks it as A, and the coloring of each node shows the status of the corresponding class when it is considered as B. The left part of the node shows the status of A ⊆ B, the right part of the node shows the status of co ⋅ A ⊆ B, and the middle part of the node shows the status of Δ ⋅ A ⊆ B (all with respect to every oracle).

Map legend: