On the applicability of Post's lattice

DOI10.1016/J.IPL.2012.02.002MaRDI QIDQ436335zbMATH OpenOpenAlexFDO

Authors Michael Thomas

Publication date 20 July 2012

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

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

zbMATH Keywords

computational complexityPost's lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Logical aspects of Boolean algebras (03G05)

Abstract: For decision problems P defined over Boolean circuits from a restricted set of gates, we have that P(B) AC0 many-one reduces to P(B') for all finite sets B and B' of gates such that all gates from B can be computed by circuits over gates from B'. In this paper, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that P(B) NC2 many-one reduces to P(B' union {and,or}) and that P(B) NC2 many-one reduces to P(B' union {false,true}), for all finite sets B and B' of Boolean functions such that all f in B can be defined in B'.

Recommendations

• The complexity of the descriptiveness of Boolean circuits over different sets of gates
• scientific article; zbMATH DE number 3978379
• The complexity of propositional implication
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

Cites work

• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• Generalized Modal Satisfiability
• Mathematical Foundations of Computer Science 2003
• Model Checking CTL is Almost Always Inherently Sequential
• Satisfiability problems for propositional calculi
• Size-depth tradeoffs for Boolean formulae
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• The Complexity of Circumscriptive Inference in Post’s Lattice
• The Complexity of Reasoning for Fragments of Default Logic
• The Parallel Evaluation of General Arithmetic Expressions
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of Boolean formula minimization
• The complexity of model checking for Boolean formulas
• The complexity of propositional implication
• The complexity of reasoning for fragments of autoepistemic logic
• The complexity of satisfiability for fragments of hybrid logic. I.
• The tractability of model-checking for LTL: the good, the bad, and the ugly fragments

Cited in

(1)

• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits

This page was built for publication: On the applicability of Post's lattice

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