Algebraic methods and bounded formulas

DOI10.1305/NDJFL/1039700695MaRDI QIDQ1377552zbMATH OpenOpenAlexFDO

Authors 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

Boolean circuit complexityexpressive power of bounded formulas in second-order arithmeticfinite modelssecond-order formulas

Mathematics Subject Classification ID

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

Recommendations

• Notes on polynomially bounded arithmetic
• scientific article; zbMATH DE number 806753
• scientific article; zbMATH DE number 440483
• Bounded arithmetic and truth definition
• Exponentiation and second-order bounded arithmetic

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• NP is as easy as detecting unique solutions
• Parity, circuits, and the polynomial-time hierarchy
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy

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

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