The limits of tractability in Resolution-based propositional proof systems

Dantchev, Stefan; Martin, Barnaby

doi:10.1016/j.apal.2011.11.001

All Outputs (2)

Parameterized Proof Complexity (2011)
Journal Article
Dantchev, S., Martin, B., & Szeider, S. (2011). Parameterized Proof Complexity. Computational Complexity, 20(1), 51-85. https://doi.org/10.1007/s00037-010-0001-1

The limits of tractability in Resolution-based propositional proof systems (2011)
Journal Article
Dantchev, S., & Martin, B. (2012). The limits of tractability in Resolution-based propositional proof systems. Annals of Pure and Applied Logic, 163(3), 656-668. https://doi.org/10.1016/j.apal.2011.11.001

We study classes of propositional contradictions based on the Least Number Principle (LNP) in the refutation system of Resolution and its generalisations with bounded conjunction, Res(k). We prove that any first-order sentence with no finite models t... Read More about The limits of tractability in Resolution-based propositional proof systems.