Theoretical computer science is a scientific discipline that is concerned with the kind of problems that computers can solve. A computer solves problems by following a certain set of instructions. Formally, these instructions are known as an algorithm. In everyday life, we often call such instructions a “computer program” or an “app”.
Some algorithms solve a problem with very few instructions, while others need to give a lot of them. The number of instructions that an algorithm gives determines whether it is fast or slow. Because everyone wants a faster computer, there is a big interest in finding the fastest algorithm for every problem. So this is one thing that occupies theoretical computer scientists.
It turns out that there are two common cases for a problem: either there exists a “fast” (polynomial time) algorithm, or only “extremely slow” (NP-complete) algorithms can be found. So problems can be categorised as either fast or extremely slow. This is known as the time complexity of the algorithm. An example of a fast problem is finding a document in a folder, which is as easy as telling the computer to read a list of documents until it finds the one it’s looking for. An example of an extremely slow problem is finding the shortest round-way trip between a large number of cities, for which the computer has to compute the distance of almost every possible route before it can tell which one is the shortest.
But there exists a handful of problems that computer scientists have found to be not extremely slow, but for which they also aren’t able to tell that they are fast. These problems seem to be somehow stuck in-between.
So obviously, one of the big questions in computer science is whether these problems are special, or whether there is a fast algorithm out there, but they just haven’t found it yet. One of these in-between problems is the “graph isomorphism problem”. This problem asks the computer to see if two graphs (simple networks) can be made to look precisely the same if the computer is only allowed to slide the nodes and stretch the connections (so the computer is not allowed to draw or or erase nodes or connections). Basically, this is just a very advanced version of untangling the christmas decorations.
One drawing of the Petersen graph [1]
Another drawing of the Petersen graph [2]
It has been known for a long time that there exists a slow but not extremely slow algorithm for this problem, but there hadn’t been any improvements for more than thirty years. Until now, that is.
In December 2015, Laszlo Babai presented a new algorithm for the graph isomorphism problem that is “almost fast” (quasi-polynomial time). It is not fast enough to be a truly fast algorithm, but it is so close that the difference is hard to spot.
Many computer scientists view this as one of the biggest breakthroughs of recent years in theoretical computer science, or at least as a huge step forward. Quanta Magazine has written an excellent long article about the graph isomorphism problem, the way the new algorithm works, and what it means to computer scientists.
Public Domain, https://commons.wikimedia.org/w/index.php?curid=357408
Public Domain, https://commons.wikimedia.org/w/index.php?curid=358837
Common sense tells us that objects of comparable size should be equally hard to find. Yet, when searching inside a random network, surprises are awaiting . . .
A mathematician once told me that problems that are very simple to state can be very deceiving, and sometimes turn out to be extremely difficult to solve. One such problem was the Four Color Problem.
Elisabeth already has an idea in mind: she would like to find the fastest possible route that goes to each address exactly once before finally returning to the station. This task is a well-known mathematical problem, namely the Traveling Salesman Problem (TSP)! How can she solve it?
Are you one of those people who always seems to pack just a bit too much for your car to handle when packing for a vacation? Then you should have a look at this article!
A conjecture of Erdős and Hajnal from 1989 says that forbidding any specific substructure results in existence of a very large homogeneous one! In this article you will have a look into one of the most fascinating problems in modern graph theory.
