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:

1. Computability — Turing Machines, Formal Languages
2. Computability — Classes of Problems, The Art of Reduction
3. Complexity — Introduction
4. Complexity — Classes and Their Limitations [THIS POST]
5. Complexity — Comparison of Different Satisfiability Problems
6. Complexity — We Don’t Know Anything Yet?

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.