Change search
ReferencesLink to record
Permanent link

Direct link
Parameterized Bounded-Depth Frege Is not Optimal
2012 (English)In: ACM Transactions on Computation Theory (TOCT), Vol. 4, no 3, 7- p.Article in journal (Refereed) Published
Abstract [en]

A general framework for parameterized proof complexity was introduced by Dantchev et al. [2007]. There, the authors show important results on tree-like Parameterized Resolution-a parameterized version of classical Resolution-and their gap complexity theorem implies lower bounds for that system. The main result of this article significantly improves upon this by showing optimal lower bounds for a parameterized version of bounded-depth Frege. More precisely, we prove that the pigeonhole principle requires proofs of size n Ω(k) in parameterized bounded-depth Frege, and, as a special case, in dag-like Parameterized Resolution. This answers an open question posed in Dantchev et al. [2007]. In the opposite direction, we interpret a well-known technique for FPT algorithms as a DPLL procedure for Parameterized Resolution. Its generalization leads to a proof search algorithm for Parameterized Resolution that in particular shows that tree-like Parameterized Resolution allows short refutations of all parameterized contradictions given as bounded-width CNFs

Place, publisher, year, edition, pages
2012. Vol. 4, no 3, 7- p.
Keyword [en]
Bounded-depth Frege, Parameterized complexity, Proof complexity, Resolution
National Category
Computer Science
URN: urn:nbn:se:kth:diva-112881DOI: 10.1145/2355580.2355582ScopusID: 2-s2.0-84868675131OAI: diva2:587528

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-05-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lauria, Massimo
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link