Algebraic methods and bounded formulas

DOI10.1305/NDJFL/1039700695zbMATH Open0889.03054OpenAlexW2081562759MaRDI QIDQ1377552FDOQ1377552

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

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

zbMATH Keywords

Boolean circuit complexityfinite modelssecond-order formulasexpressive power of bounded formulas in second-order arithmetic

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)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Title not available (Why is that?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parity, circuits, and the polynomial-time hierarchy
• NP is as easy as detecting unique solutions
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Title not available (Why is that?)
• 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)