## complexity

The simple act of packing your luggage can open a complex can of worms.

How fast can you tell whether two networks are the same?

Are there problems computers will never be able to solve, no matter how powerful they become?

A famous question involving networks appears to have come closer to an answer.

What will quantum computers be able to do that ordinary computers can't do?

Kolmogorov complexity gives a high value to strings of symbols that are essentially random. But isn't randomness essentially meaningless? Should a measure of information assign a low value to it? The concept of sophistication addresses this question.

There are many ways of saying the same thing — you can use many words, or few. Perhaps information should be measured in terms of the shortest way of expressing it? In the 1960s this idea led to a measure of information called *Kolmogorov complexity*.

Can you measure information? It's a tricky question — but people have tried and come up with very interesting ideas.

On the face of it the Universe is a fairly complex place. But could mathematics ultimately lead to a simple description of it? In fact, should simplicity be a defining feature of a "theory of everything"? We ponder the answers.

In this, the second part of this series, we look at a mathematical notion of complexity and wonder whether the Universe is just too complex for our tiny little minds to understand.