**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:

- Computability — Turing Machines, Formal Languages
- Computability — Classes of Problems, The Art of Reduction
- Complexity — Introduction
- Complexity — Classes and Their Limitations
**[THIS POST]** - Complexity — Comparison of Different Satisfiability Problems
- 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?**