# ^^Complessita' in informatica.

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

## 3 Big Three Ideas in Complexity theory

- Boolean strings
- Problems
- Classes

## Boolean strings

The starting insight is that

- we can use boolean strings to represent all our
basic objects.

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 ...

- It is implicitly assumed that everyone will
convert that to Let {x} be a string {x_1 x_2 ... x_m } of {0}‘s and {1}‘s that
encodes the number in the usual way.

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.

## Problems

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.

## Classes

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.