WHY EVEN IN THE AGE OF AI, SOME PROBLEMS ARE JUST TOO DIFFICULT

Empowered by artificial intelligence technologies, computers today can engage in convincing conversations with people, compose songs, paint paintings, play chess and go, and diagnose diseases, to name just a few examples of their technological prowess. These successes could be taken to indicate that computation has no limits. To see if that’s the case, it’s important to understand what makes a computer powerful.

There are two aspects to a computer’s power: the number of operations its hardware can execute per second and the efficiency of the algorithms it runs. The hardware speed is limited by the laws of physics. Algorithms – basically sets of instructions – are written by humans and translated into a sequence of operations that computer hardware can execute. Even if a computer’s speed could reach the physical limit, computational hurdles remain due to the limits of algorithms.

These hurdles include problems that are impossible for computers to solve and problems that are theoretically solvable but in practice are beyond the capabilities of even the most powerful versions of today’s computers imaginable. Mathematicians and computer scientists attempt to determine whether a problem is solvable by trying them out on an imaginary machine.

AN IMAGINARY COMPUTING MACHINE
The modern notion of an algorithm, known as a Turing machine, was formulated in 1936 by British mathematician Alan Turing. It’s an imaginary device that imitates how arithmetic calculations are carried out with a pencil on paper. The Turing machine is the template all computers today are based on.

To accommodate computations that would need more paper if done manually, the supply of imaginary paper in a Turing machine is assumed to be unlimited. This is equivalent to an imaginary limitless ribbon, or “tape,” of squares, each of which is either blank or contains one symbol.

NOT EVERY PROBLEM CAN BE SOLVED
Many problems are solvable using a Turing machine and therefore can be solved on a computer, while many others are not. For example, the domino problem, a variation of the tiling problem formulated by Chinese American mathematician Hao Wang in 1961, is not solvable.

The task is to use a set of dominoes to cover an entire grid and, following the rules of most dominoes games, matching the number of pips on the ends of abutting dominoes. It turns out that there is no algorithm that can start with a set of dominoes and determine whether or not the set will completely cover the grid.

KEEPING PROBLEMS REASONABLE
A number of solvable problems can be solved by algorithms that halt in a reasonable amount of time. These “polynomial-time algorithms” are efficient algorithms, meaning it’s practical to use computers to solve instances of them.

Thousands of other solvable problems are not known to have polynomial-time algorithms, despite ongoing intensive efforts to find such algorithms. These include the Traveling Salesman Problem.

The Traveling Salesman Problem asks whether a set of points with some points directly connected, called a graph, has a path that starts from any point and goes through every other point exactly once, and comes back to the original point. Imagine that a salesman wants to find a route that passes all households in a neighborhood exactly once and returns to the starting point.

THE COST OF KNOWING EXACTLY
The best-known algorithms for NP-complete problems are essentially searching for a solution from all possible answers. Traveling Salesman Problem on a graph of a few hundred points would take years to run on a supercomputer. Such algorithms are inefficient, meaning there are no math shortcuts.

Practical algorithms that address these problems in the real world can only offer approximations, though the approximations are improving. Whether there are efficient polynomial-time algorithms that can solve NPcomplete problems is among the seven millennium open problems posted by the Clay Mathematics Institute at the turn of 21st century, each carrying a prize of US$1 mn.

NEW COMPUTATION FORM BEYOND TURING
Could there be a new form of computation beyond Turing’s framework? In 1982, American physicist Richard Feynman, a Nobel laureate, put forward the idea of computation based on quantum mechanics.

In 1995, Peter Shor, an American applied mathematician, presented a quantum algorithm to factor integers in polynomial time. Mathematicians believe that this is unsolvable by polynomialtime algorithms in Turing’s framework. Factoring an integer means finding a smaller integer greater than 1 that can divide the integer. For example, the integer 688,826,081 is divisible by a smaller integer 25,253, because 688,826,081 = 25,253 x 27,277.

SOURCE: THE CONVERSATION