Algebraic methods and bounded formulas

DOI10.1305/ndjfl/1039700695zbMath0889.03054OpenAlexW2081562759MaRDI QIDQ1377552

Domenico Zambella

Publication date: 14 June 1998

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1039700695

zbMATH Keywords

finite modelsBoolean circuit complexitysecond-order formulasexpressive power of bounded formulas in second-order arithmetic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• NP is as easy as detecting unique solutions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parity, circuits, and the polynomial-time hierarchy
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy

This page was built for publication: Algebraic methods and bounded formulas