An upper bound for the circuit complexity of existentially quantified Boolean formulas

DOI10.1016/J.TCS.2010.04.017MaRDI QIDQ982657zbMATH OpenOpenAlexFDO

Authors Hans Kleine Büning, Anja Remshagen

Publication date 7 July 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.04.017

zbMATH Keywords

circuitscomplexityquantified Boolean formulas

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27)

Recommendations

• Bounds on an exponential sum arising in Boolean circuit complexity
• Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity
• scientific article; zbMATH DE number 5139037
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency
• Proof Complexity of Quantified Boolean Logic — A Survey
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• Lower bounds for unrestricted Boolean circuits: open problems
• Lower bounds for Boolean circuits of bounded negation width

Cites work

• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3668579 (Why is no real title available?)
• scientific article; zbMATH DE number 1342212 (Why is no real title available?)
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• The complexity of facets resolved

Cited in

(4)

• Transformations into normal forms for quantified circuits
• scientific article; zbMATH DE number 5139037 (Why is no real title available?)
• Circuit complexity and the expressive power of generalized first-order formulas
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency

This page was built for publication: An upper bound for the circuit complexity of existentially quantified Boolean formulas

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