Monday, June 24, 2019
Speaker: Mateus de Oliveira Oliveira
Venue: TU Wien, Favoritenstr. 9-11, FAV Hörsaal 2
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.