Function-algebraic characterizations of log and polylog parallel time

DOI10.1007/BF01202288zbMath0813.68099MaRDI QIDQ1332666

Stephen Bloch

Publication date: 1 September 1994

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

computational complexity classes

Mathematics Subject Classification ID

Circuits, networks (94C99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (8)

Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ On parallel hierarchies and R ki ⋮ Computation models and function algebras ⋮ A Characterization of NC k by First Order Functional Programs ⋮ A characterization of alternating log time by ramified recurrence ⋮ Unnamed Item ⋮ On the computational complexity of imperative programming languages ⋮ Implicit characterizations of FPTIME and NC revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On uniform circuit complexity
• Arithmetizing uniform \(NC\)
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• A bounded arithmetic AID for Frege systems
• An algebra and a logic for \(NC^ 1\)

This page was built for publication: Function-algebraic characterizations of log and polylog parallel time