Some Width Measures for Proofs

FORSYTE/RiSE hosted a talk by Mateus de Oliveira Oliveira

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.

CONTACT

Laura Kovacs

Mateus de Oliveira Oliveira, Bergen University