The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Workshop

New Directions in Proof Complexity

Parametrised Proof Complexity

Author: S Dantchev (University of Durham)

Abstract

Motivated by the well known concept of Fixed-Parameter Tractability, we initiate research in an area that we call Parametrised Proof Complexity. We first give a Cook-Rekhow-style definition of a parametrised proof system, and then relate the (im)possibility of existence of a fixed-parameter tractable (FPT) proof system to the FPT vs W[2] question. We observe that the most popular method for designing fixed-parameter algorithms, Bounded Search Tree, corresponds to Tree-like Resolution in the context of parametrised proof systems, and give some upper and lower bounds for the latter. We finally discuss and prove some dichotomy results (also called complexity gap theorems) for weak relativised proof systems.

This is a work in progress, joint with B. Martin and S. Szeider.