Can a problem be solved well enough within a reasonable time – or is it impossible because it demands excessive computational resources? These are questions being examined in a research project at KTH Royal Institute of Technology, where basic mathematical research may yield results with major implications.
Project Grant 2016
Approximability and proof complexity
Principal investigator:
Johan Håstad, Professor of Computer Science
Co-investigators:
Per Austrin
Jakob Nordström
Institution:
KTH Royal Institute of Technology
Grant in SEK:
SEK 32.2 million over five years
Imagine an airline trying to deploy its flight crews in the best way: who should sleep when and who should fly where? Or the task of finding the shorting traveling distance for a salesperson who has to travel to a number of cities and then home again, known as the “traveling salesman problem”.
If only a few places or individuals are involved, such problems are not difficult to solve. But when the size of the problem grows, the time required to find the optimum solution increases dramatically. Testing every conceivable solution takes an unreasonably long time, even for the fastest computers.
Johan Håstad and his colleagues at KTH are studying problems of this kind, known as “NP problems”, in a project funded by the Knut and Alice Wallenberg Foundation.
“Most of all I’m trying to show that problems are difficult. Perhaps we shouldn’t try to solve them, because they take too long, or we should simplify them or only solve the problem in certain simpler instances.”
The researchers are trying to find better algorithms to solve difficult computational problems. If, for example, it takes a million years to find the optimum solution to a given problem, it might be possible to find a fairly good solution in just one minute. A key issue is then deciding how good “fairly good” is. Håstad elaborates:
“One thing we want to do is to create algorithms that always produce an answer that is no more than ten percent worse than the best solution – not that experience tells us this is so, but that we are able to prove mathematically that this is always the case.”
Examining proof
The project combines the search for such “approximation algorithms” with the neighboring field of “proof complexity”.
Say you have a control system for a railroad yard, and set all the thousands of switches according to the rules. Could two trains ever end up on a collision course? The reply “it could never happen” doesn’t say much – how do you know it’s true?
“Here, you want a formal system of proof, which row by row can prove it can never happen. An important point is that the assertion can then be verified by someone else,” Håstad explains.
Among other things, the researchers are studying the length of such proof. In the railroad yard example the proof may be too long to be accommodated in a normal computer.
“Proof normally exists, but the question is what length is required, and how complicated the intermediate results need to be.”
Important model problems
The KTH researchers are working on a number of model problems that are well known in mathematics. They hope to gain a deeper understanding of them, which will give them general insights to distinguish easy computational problems from difficult ones.
“It’s very much a question of comparing different problems. This is a common way of showing that something is difficult – namely to prove it is as difficult as a problem we already know is difficult,” Håstad adds.
Final solutions may not be achieved within the five-year span of the project, but important steps may well be made along the way. For instance, Håstad wants to improve the solution of the classic “traveling salesman problem” – the salesperson who must visit a number of towns taking the shortest possible route. An algorithm from the 1970s supplies an answer within 50 percent of the optimum solution, but it is not known whether that is the best that can be done.
“So far we have shown that we cannot get within just one percentage point of the best solution. But it would really be fun to improve this lower bound.”
Million-dollar prize
An important question being addressed by the researchers is called P=NP? Simply put, P denotes the set of problems that are efficiently solvable; a solution can be achieved within a reasonable time. NP are problems whose solution can be effectively verified once it is known. The question is then: if it is so easy to find the answer to a problem, is it then always easy to verify the answer?
The problem was stated in the 1970s, and many mathematicians do not believe that P is equal to NP. But no-one has yet managed to prove it. The first person to find a general solution will receive a prize of one million US dollars from the Clay Mathematics Institute in the U.S. At the time of the new millennium, the institute founded a prize for solving seven central mathematical problems.
The project at KTH Royal Institute of Technology involves basic research. But there are many potential applications on the horizon, and the results may in some cases have major implications. For instance, at present sensitive information on the internet is protected using an encryption method exploiting the fact that there are currently no algorithms capable of factoring large whole numbers within a reasonable time. Factoring means dividing up into factors, i.e. expressing the number as a product of lesser numbers.
“If we found such an algorithm – if it were suddenly possible to factorize large whole numbers – we would have to redesign the entire internet security infrastructure,” Håstad points out.
Text Sara Nilsson
Translation Maxwell Arding
Photo Magnus Bergström
