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

DOI10.1016/j.tcs.2010.04.017zbMath1192.68637OpenAlexW2053550065MaRDI QIDQ982657

Anja Remshagen, Hans Kleine Büning

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

complexitycircuitsquantified Boolean formulas

Mathematics Subject Classification ID

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

Cites Work

• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• The complexity of facets resolved
• Complete sets and the polynomial-time hierarchy
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Unnamed Item
• Unnamed Item

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