Skip to content

LAA

Seminar

Parametrised proof complexity

Dantchev, S (Durham)
Thursday 13 April 2006, 11:30-12:30

Seminar Room 1, Newton Institute

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.

Presentation

[pdf ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧