Project receives EUR 3.2 million to explore limits of efficient computability
Research dealing with complex computational problems and the methods for solving them is one of the projects at KTH that recently received funding from the Knut and Alice Wallenberg Foundation.
In computational complexity theory, one central question is to understand which problems can be solved within a reasonable amount of time, and which problems are practically impossible because they require excessive computer resources.
Now three KTH researchers have received EUR 3.2 million over five years to jointly study these computational problems. The focus of their project is to conduct fundamental research on what are known as NP-hard problems.
“This project is a contribution toward the long term and worldwide project of trying to understand efficient computation,” says Johan Håstad , Professor in computer science in the Group at KTH.
NP-hard problems arise in many contexts, some of which may involve scheduling, network design or different types of planning.
The best-known of example of an NP-hard problem is the traveling salesman problem (TSP), which asks the following: given a set of cities and the distances between them, is there a route that allows the salesmen to visit them all in less than x distance?
Other planning issues that are NP-hard can include how to allocate frequencies to mobile towers in order to minimize interference problems, or to schedule airline crews in the best way.
Ever since such problems have been studied, beginning in the 1970s, finding optimal solutions has remained computationally difficult. Håstad says that he and fellow KTH researchers Per Austrin and Jacob Nordström will study whether it is possible to find demonstrably good, approximate solutions within a reasonable amount of time. Algorithms that succeed in doing so are called approximation algorithms.
Proof Complexity is an adjacent area which explores the length of a proof of logical formulas in various formal systems.
Such a logical formula, for example, could say that if certain specified rules are followed for setting switches in a railroad yard, then a head-on collision between two trains becomes impossible. Even if true, the proof of the formula may exceed the capacity of a powerful computer if the railroad yard is large with many switches.
In its study, the researchers will look at what problems are efficiently solvable, and which ones are not.
New methods for constructing effective solutions may lead to new results in both approximation and proof complexity – areas that were previously separate areas of research.
While the project is fundamental research, the impact is potentially broad. “It may impact any application in society where the available amount of computational resources is the bottleneck,” Håstad says.
The research project is titled "Approximability and proof complexity" .
Peter Ardell