P-uniform circuit complexity
From MaRDI portal
Publication:3474881
DOI10.1145/76359.76370zbMath0697.68031OpenAlexW2095274905MaRDI QIDQ3474881
Publication date: 1989
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/76359.76370
parallelismsparse setsexponential timetally setsalternating Turing machinecomplexity hierarchiesauxiliary pushdown automataalternation and nondeterminismbounded-action devicesprecompositionreducibility and completeness
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
On uniformity within \(NC^ 1\), Some results on uniform arithmetic circuit complexity, Expressing uniformity via oracles, Amplifying circuit lower bounds against polynomial time, with applications, Polynomial games and determinacy, Subclasses of \textsc{Ptime} interpreted by programming languages, Extensional Uniformity for Boolean Circuits, Deciding bisimilarity is P-complete, Tradeoff lower lounds for stack machines, Some classes of languages in \(NC^ 1\), Non-commutative arithmetic circuits: depth reduction and size lower bounds, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, The complexity of computing maximal word functions
