Circuit Bottom Fan-in and Computational Power
From MaRDI portal
Publication:4388876
DOI10.1137/S0097539795282432zbMath0907.68077OpenAlexW1984645675WikidataQ56959065 ScholiaQ56959065MaRDI QIDQ4388876
Johan T. Håstad, Jian'er Chen, Li-Ming Cai
Publication date: 10 May 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795282432
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the existence of subexponential parameterized algorithms ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Gap-languages and log-time complexity classes ⋮ Programs over semigroups of dot-depth one