skip to content

Parametrised proof complexity

Thursday 13th April 2006 - 11:30 to 12:30
INI Seminar Room 1

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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons