Computational complexity

The general area

Solving a computational problem requires resources and the fundamental question studied in this research area is to determine, as closely as possible, the computational difficulty of basic problems. This general question has many flavors as there are many different types of resources and many different computational problems. As larger instances of the same problem are harder to solve the key object to study is how resources consumed grow as a function of the size of the input.

The best known resource is time, which is measured as the number of elementary operations needed to solve the problem at hand. A theoretical notion, that mostly agrees well with practice, is that a problem is efficiently solvable if and only if it can be solved by an algorithm with running time that grows as a polynomial function of the size of the inputs. The most famous problem in complexity theory is whether NP equals P. In every day terms this is the question whether for any problem where a good solution can be verified efficiently can such a solution can also be found efficiently.

Results in algorithms and complexity comes in two different forms. Algorithmic results where algorithms are designed and analyzed and hardness results, where a proof, possibly using a well established conjecture such as NP is not in P, is given that a computational problem requires large resources.

Approximation algorithms

For problems where it is known that it is hard to find the globally optimal solution it is possible to have efficient algorithms that finds a solution of provably good quality. One example is to find a solution that is only 10% worse than the optimal solution. We are interested in proving both the existence and noneexistence of such algorithms. In some other situations it is interesting to look for algorithms running in mildly exponential time.

Proof complexity and Sat-solvers

In some situations it might be possible to spend a long time looking for a solution but it is crucial that there is a short proof that the answer is correct. This proof might be done in a number of different formalisms and this results in a rich set of questions. The study of one such formalism called resolution is tied closely to the study of algorithms for satisfiability so called Sat-solvers. Somewhat surprisingly this NP-complete problem has algorithms capable of solving many instances appearing in practice.

Dynamic and distributed algorithms

Modern information is hard for computers to process because it scatters in many places and changes rapidly, among other reasons. We are studying mathematical questions that might lead to better ways (algorithms) for computers to handle such information.

When information changes we speak of dynamic algorithms and when each processor only controls a small fraction of the input we call this distributed computation. Somewhat surprisingly there are similarities between these situations and we are currently exploring these.

About

Researchers

Funding

ERC, KAW, VR

Top page top