Output details
11 - Computer Science and Informatics
University of Durham
Article title
The limits of tractability in Resolution-based propositional proof systems
Type
D - Journal article
Title of journal
Annals of Pure and Applied Logic.
Article number
-
Volume number
163
Issue number
3
First page of article
656
ISSN of journal
0168-0072
Year of publication
2012
Number of additional authors
1
Additional information
<10>The paper is a step towards a full characterisation of resolution complexity of propositional contradictions expressible in first-order logic. Atserias and Oliva have since followed up by systematising our approach and trying to create a general theory of interpretations (in a model-theoretic sense) that preserve the resolution complexity of a first-order sentence. (See Oliva's PhD thesis “On the Complexity of Resolution-based Proof Systems”, Universitat Politecnica de Catalunya, 2013, subsection 1.3.2, Definability and interpretability, the summary of their result.)
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Algorithms and Complexity Research Group
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
