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?