On the applicability of Post's lattice

DOI10.1016/J.IPL.2012.02.002zbMATH Open1243.68193arXiv1007.2924OpenAlexW1859310323MaRDI QIDQ436335FDOQ436335

Authors: Michael Thomas 

Publication date: 20 July 2012

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

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'.

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

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

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)

Cites Work

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

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)