Complexity Theory

Complexity theory is a subfield of computer science. It does not ask whether a computer can solve a problem, but how costly that is – measured in time and memory requirements. Both quantities depend on how large the problem is. Sorting a list of ten entries takes a short time; sorting a list of a billion entries takes much longer. Complexity theory describes this relationship with mathematical precision and divides problems into classes depending on how strongly the effort grows with the problem size.

Why some problems are practically unsolvable

There are problems for which no algorithm is known that solves them quickly. In complexity theory, quickly means: the effort grows at most as a polynomial of the problem size – for example quadratically or cubically. If it grows exponentially instead, the computing time doubles with every additional element. With twenty elements this is still manageable, but with a hundred it already becomes astronomical.

A well-known example is the Travelling Salesman Problem: a salesman is supposed to visit every city on his route exactly once while choosing the shortest total distance. With five cities there are only twelve possible routes. With twenty cities there are already more than 60 trillion. No computer in the world can try out all of them once the number of cities keeps increasing. Such problems are considered practically unsolvable – not because computers are built too slowly, but because the underlying mathematics dictates it that way.

Complexity classes: P, NP, and the great open riddle

The best-known classes are called P and NP. Class P contains problems that a computer can solve quickly. Class NP contains problems where a proposed solution can be verified quickly, but not necessarily found quickly on its own. The Travelling Salesman Problem belongs to NP: whether a particular route really is the shortest can easily be checked – but finding the shortest route itself is hard.

The open question is: Is P equal to NP? In other words: does every problem whose solution can be verified quickly also have an algorithm that finds it quickly? Most computer scientists believe the answer is no – but this has not been proven to this day. It is one of the most famous unsolved problems in mathematics, carrying a one-million-dollar prize offered by the Clay Mathematics Institute.

Besides these, there are further classes, such as PSPACE for problems with limited memory requirements or BQP for problems that a quantum computer can solve efficiently. This map of difficulty levels is the core of complexity theory.

Significance for AI, cryptography, and everyday products

Cryptography – the encryption of data – is one of the most important application areas. HTTPS, the protocol behind every secure website visit, relies on the fact that certain mathematical problems lie in NP. Multiplying a number is easy; finding the two large prime factors of a huge number is extremely hard. The security of modern encryption literally depends on P ≠ NP holding true.

Complexity theory also plays a role in AI. Many optimization problems – such as training neural networks or planning routes in navigation apps – are NP-hard. In practice, approximation methods known as heuristics are therefore used, which do not guarantee an optimal solution but deliver a sufficiently good one within a reasonable time. Google Maps finds a very good route in seconds, but not necessarily the mathematically best one among all possibilities.

Complexity theory comes up in tech news when quantum computers are reported on. Quantum computers promise to solve certain problems from NP faster. Whether they fundamentally expand the class P or even prove P = NP, however, remains open. Anyone wanting to make sense of such headlines needs exactly the basic understanding that complexity theory provides.