On ACC (Q1346616)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	On ACC	scientific article

Statements

scholarly article

0 references

On ACC (English)

0 references

0 references

0 references

Computational Complexity

0 references

publication date

6 April 1995

0 references

zbMATH Keywords

ACC

0 references

modulus-amplifying polynomials

0 references

MaRDI profile type

MaRDI publication profile

0 references

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

Depth reduction for circuits of unbounded fan-in

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

0 references

Finite monoids and the fine structure of <i>NC</i> <sup>1</sup>

0 references

Counting classes: Thresholds, parity, mods, and fewness

0 references

PP is closed under intersection

0 references

0 references

Constant Depth Reducibility

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

A circuit-based proof of Toda's theorem

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy

0 references

PP is as Hard as the Polynomial-Time Hierarchy

0 references

Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy

0 references

full work available at URL

https://doi.org/10.1007/bf01263423

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/BF01263423

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1346616

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1346616&oldid=37101631"