Content about “

complexity

”

We talk to pioneering mathematician Stephen Cook, who came up with the concept of NP-complete problems, about his work, computer science, and artificial intelligence.

Quantum particles that are both light and matter help solve infamous NP hard problems.

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.