**Complexity — Classes and Their Limitations**

This is Part 4 of Series: “How To Explain Complexity Theory To Your Buddy”. You can check my all posts here:

**Complexity Classes**

Previously, we have seen some special cases of classes like O(1), O(n) but didn’t really touch how to identify algorithmic problems based on their similar characteristics. Let’s do a quick recap of classes:

- A class is a set of languages containing languages of similar behaviour. It analyzes how efficient resources (time / space) are used at the edge of infinity.
- Given X is a class, a X-hard problem is equally or more difficult than any problem in X, a X-complete problem is the one of the most difficult problems in X.

**Class Hierarchy**

Now that we have learnt the fundamentals of computability and complexity, we will learn about the most basic complexity classes such as P and NP. To show how they would look like in real life, I couldn’t find a better way to show than chess. A chess position is given below where it is black player’s turn:

*P*:

*Formal definition*: A Deterministic Turing Machine decides in polynomial time if at least an input value is accepted.*Characteristics*: The code contains loops and simple recursions with a polynomial time bound.*Game Perspective*: For this to be succeeded, the whole system must be known by all nodes in the system, there is no such thing as searching other nodes or players.*A Most Expressive Problem*: Horn-Satisfiability (HORNSAT)*A Chess Problem*:**Which moves can black player make?**

*NP*:

*Formal definition*: A Nondeterministic Turing Machine decides in polynomial time if at least an input value is accepted.*Characteristics:*The code contains at least one loop iterating exponentially or a recursive searching algorithm is implemented.*Game Perspective*: One player explores a whole system starting from a node and gaining more information.*A Most Expressive Problem*: Boolean Satisfiability (SAT)*A Chess Problem*:**Can black player technically win the round?**

*co-NP*:

*Formal definition*: A Nondeterministic Turing Machine decides in polynomial time if every input value is accepted.- Characteristics and game perspective are similarly defined as NP
*A Most Expressive Problem*: Boolean Tautology (TAUT)*A Chess Problem*:**Does white player lose at all scenarios?**

*PSPACE*:

*Formal definition*: A Nondeterministic Turing Machine requires polynomial space in order to decide in polynomial time if at least an input value is accepted.*Characteristics*: The code contains multiple algorithms with searching capabilities as in NP, which can only respond to others’ previous moves in sequential order.*Game Perspective*: Multiple players with different strategies, which behave differently based on another player’s moves. The strategies of players are saved in polynomial space.*A Most Expressive Problem*: Satisfiability for Quantified Boolean Formulas (QSAT)*A Chess Problem*:**Does black player have a winning strategy?**

*EXPTIME*:

*Formal definition*: A Deterministic Turing Machine decides in exponential time if at least an input value is accepted.*Characteristics*: Given multiple algorithms having different strategies as in PSPACE, each algorithm knows only a subset of the previous decisions of others’.*Game Perspective*: Multiple players, which not only behave differently based on other players’ previous moves, but also may have incomplete information about the current game status / move history when making a move.*A Most Expressive Problem*: Satisfiability for Dependency Quantified Boolean Formulas (DQSAT)*A Chess Problem*:**Is black player more likely going to win the game?**

The higher we go in complexity hierarchy, the less information we generally have access to. A quick recap:

*P vs NP*: In P, it has**total**information about the whole system; however in NP, it starts with**partial**information from a node in the system and explores to find an optimal solution.*(co-)NP vs PSPACE*: In (co-)NP, there is only one player (or multiple players working**cooperatively**) making a move to find an optimal solution; however in PSPACE, the player**cannot guess**the move of the others with certainty, so it has strategy instead.*PSPACE vs EXPTIME*: In PSPACE, a player has a winning strategy at some point knowing the**whole**current game status; however in EXPTIME, a player**cannot know**the whole current game status.