Abstract:

In traditional complexity theory, the complexity of computational problems is

measured as a function of the size of the input. Nevertheless, in many situations

of practical relevance, analyzing the complexity of a problem only taking the size

of the input into consideration may not reflect the difficulty of solving that particular

problem on practical instances. Indeed, there are plenty of examples where a problem

is NP-hard but which can be solved efficiently by standard algorithms on empirically

inspired benchmarks. In parameterized complexity theory, the complexity of a problem

is measured not only in terms of the size of the input but also in terms of additional parameters that try to capture structural properties of the problem in question. In some cases, parameterized complexity theory offers a reasonable explanation of why such problems are solvable efficiently in practice: very often on practical instances, the parameters of relevance have small magnitude.

Most work in parameterized complexity theory deals with showing that certain NP-complete problems can be solved efficiently when certain relevant parameters are fixed. Nevertheless, not much has been done in classifying the parameterized complexity of problems that extremely hard from the perspective of classical complexity. In this talk, I will discuss a framework that allows

one to bring traditional tools of parameterized complexity theory to the realm of proof theory. In particular, we will define a suitable notion of width for proofs and will show how to construct proofs of small width in polynomial time.