Parameterized resolution with bounded conjunction

DOI10.1007/978-3-642-38536-0_12MaRDI QIDQ4928479zbMATH OpenOpenAlexFDO

Authors Barnaby Martin, Stephan Stoyanov Danchev

Publication date 14 June 2013

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.2983

Mathematics Subject Classification ID

Complexity of proofs (03F20) Analysis of algorithms and problem complexity (68Q25)

Abstract: We provide separations between the parameterized versions of Res(1) (Resolution) and Res(2). Using a different set of parameterized contradictions, we also separate the parameterized versions of Res*(1) (tree-Resolution) and Res*(2).

Recommendations

• Relativization makes contradictions harder for resolution
• Parameterized proof complexity
• Relativisation Provides Natural Separations for Resolution-Based Proof Systems
• Parameterized bounded-depth Frege is not optimal
• Exponential separation between Res(k) and Res(k+1) for k n

Cited in

(3)

• Relativization makes contradictions harder for resolution
• scientific article; zbMATH DE number 35423 (Why is no real title available?)
• scientific article; zbMATH DE number 1929954 (Why is no real title available?)

This page was built for publication: Parameterized resolution with bounded conjunction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928479)