On the number of quantifiers needed to define Boolean functions

DOI10.4230/LIPICS.MFCS.2024.34MaRDI QIDQ7241035zbMATH OpenFDO

Authors Marco L. Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.34

zbMATH Keywords

Boolean functionscombinatorial gameslogicquantifier number

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Note on Sparse Complete Sets
• An application of games to the completeness problem for formalized theories
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 3285248 (Why is no real title available?)
• Number of quantifiers is better than number of tape cells
• On the number of quantifiers as a complexity measure
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The Size of a Formula as a Measure of Complexity
• The succinctness of first-order logic on linear orders

Cited in

(1)

• Description complexity of unary structures in first-order logic with links to entropy

This page was built for publication: On the number of quantifiers needed to define Boolean functions

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