scientific article; zbMATH DE number 549850
From MaRDI portal
Publication:4287354
zbMath0797.68064MaRDI QIDQ4287354
Publication date: 12 April 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
circuit complexityexplicit constructionapproximately counting circuitsnumber of 1's in a 0-1 sequence of length \(n\)
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Expander-based cryptography meets natural proofs ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Randomness buys depth for approximate counting ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On algorithmic statistics for space-bounded algorithms ⋮ On the Optimal Compression of Sets in PSPACE ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ On extracting space-bounded Kolmogorov complexity