Algebraic methods and bounded formulas
type: Item
instance of: scholarly article
title: Algebraic methods and bounded formulas
zbMATH Open document ID: 0889.03054
author: Domenico Zambella
published in: Notre Dame Journal of Formal Logic
publication date: 1998-06-14T00:00:00Z
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 1109537
zbMATH Keywords: expressive power of bounded formulas in second-order arithmetic
zbMATH Keywords: second-order formulas
zbMATH Keywords: finite models
zbMATH Keywords: Boolean circuit complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1039700695
OpenAlex ID: W2081562759
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Q3241504
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q4850554
cites work: Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: NP is as easy as detecting unique solutions
DOI: 10.1305/NDJFL/1039700695
description: scientific article; zbMATH DE number 1109537