Rudimentary reductions revisited

DOI10.1016/0020-0190(91)90015-AzbMath0748.68017OpenAlexW2003704103MaRDI QIDQ1183444

Eric W. Allender, Vivek K. Gore

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90015-a

zbMATH Keywords

computational complexityformal languagestheory of computationrudimentary reductions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication., The minimum oracle circuit size problem, The isomorphism conjecture for constant depth reductions, Fifty years of the spectrum problem: survey and new results, A constant-space sequential model of computation for first-order logic, Investigations Concerning the Structure of Complete Sets, A constant-space sequential model of computation for first-order logic, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, The complexity of computing maximal word functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniform circuit complexity
• Corrigendum: Space-bounded reducibility among combinatorial problems
• On uniformity within \(NC^ 1\)
• Theory of Formal Systems. (AM-47)
• Parity, circuits, and the polynomial-time hierarchy
• The role of rudimentary relations in complexity theory
• An Optimal Parallel Algorithm for Formula Evaluation
• Rudimentary Predicates and Relative Computation
• Expressibility and Parallel Complexity