The complexity of propositional implication

DOI10.1016/J.IPL.2009.06.015MaRDI QIDQ989577zbMATH OpenOpenAlexWikidataFDO

Authors J. Martínez

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityPost's latticepropositional implication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficentily solvable only if the connectives are definable using the constants {false,true} and only one of {and,or,xor}. The problem remains coNP-complete in all other cases. We also consider the restriction of G to singletons.

Recommendations

• The complexity of the falsifiability problem for pure implicational formulas
• Polynomial-time inference of all valid implications for Horn and related formulae
• A note on the computational complexity of the pure classical implication calculus
• The complexity of minimum partial truth assignments and implication in negation-free formulae
• The complexity of circumscriptive inference in Post's lattice

Cites work

• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Constant Depth Reducibility
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• Satisfiability problems for propositional calculi
• Structure and importance of logspace-MOD class
• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• The Complexity of Reasoning for Fragments of Default Logic
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(20)

• A note on the computational complexity of the pure classical implication calculus
• The complexity of minimum partial truth assignments and implication in negation-free formulae
• Lewis dichotomies in many-valued logics
• An unexpected Boolean connective
• Isomorphic implication
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• The Complexity of Reasoning for Fragments of Default Logic
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• On the applicability of Post's lattice
• scientific article; zbMATH DE number 4114609 (Why is no real title available?)
• Sets of Boolean connectives that make argumentation easier
• On the parameterized complexity of non-monotonic logics
• Mathematical Foundations of Computer Science 2005
• Logic for Programming, Artificial Intelligence, and Reasoning
• The weight in enumeration
• The complexity of the falsifiability problem for pure implicational formulas
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
• Strong backdoors for default logic
• Strong backdoors for default logic
• The complexity of circumscriptive inference in Post's lattice

This page was built for publication: The complexity of propositional implication

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