^^Complessita' in informatica.

credits: rjlipton/what-is-a-complexity-class

3 Big Three Ideas in Complexity theory

  1. Boolean strings
  2. Problems
  3. Classes

Boolean strings

The starting insight is that

From integers to matrices, from permutations to groups, we can and do use strings of {0}‘s and {1}‘s to represent them. Strings are the basic building blocks that we use every day in complexity theory.

We say all the time, Let {x} be an natural number ...

I believe the first to talk at length about binary numbers was the great Gottfried Leibniz. He was not the first to discover the binary system, but he did write at about it in his Explication de l’Arithm’tique Binaire in 1703. Also see the original here.


The definition of a problem is simple: a problem is nothing more than a set of strings.

This is one of the simplest definitions in mathematics, yet it is really quite important. The notion of a problem as a formal mathematical object allows us to study problems, without this definition a problem would be a vague notion. I think that one of the great achievements of theory is the formalization of the “problem” notion.

In the early days of theory problems were usually called languages. A language {L} was just a set of strings.

The reason they were called languages initially is based on the early motivations of the field. The initial questions were driven by two types of languages: natural languages and artificial ones. Certainly Noam Chomsky and many others were interested in trying to model real languages, such as English. Others were driven by their interest in computer programming languages. 


A family of problems is called a complexity class. It is that general, that simple, and that elegant. Any such family is a complexity class. But as in the famous book Animal Farm by George Orwell:

All complexity classes are equal, but some complexity classes are more equal than others.