Function-algebraic characterizations of log and polylog parallel time

DOI10.1007/BF01202288MaRDI QIDQ1332666zbMATH OpenFDO

Authors Stephen Bloch

Publication date 1 September 1994

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01202288

zbMATH Keywords

computational complexity classes

Mathematics Subject Classification ID

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

Review text

Could computational complexity classes be described without reference to Turing machines or other specific computation models? In 1965, Cobham gave a ``Yes answer for the class of polynomial-time computable functions. He showed that this class is the algebra generated from a few base functions by closure under composition and a form of recursion. In this paper, the author presents similar results for two parallel complexity classes.

Recommendations

• scientific article; zbMATH DE number 176199
• Algebraic and logical characterizations of deterministic linear time classes
• scientific article; zbMATH DE number 1390027
• A new recursion-theoretic characterization of the polytime functions
• scientific article; zbMATH DE number 1956513

Cites work

• A bounded arithmetic AID for Frege systems
• A new recursion-theoretic characterization of the polytime functions
• An algebra and a logic for \(NC^ 1\)
• Arithmetizing uniform NC
• Bounded arithmetic for NC, ALogTIME, L and NL
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 440478 (Why is no real title available?)
• scientific article; zbMATH DE number 176211 (Why is no real title available?)
• On uniform circuit complexity

Cited in

(15)

• Implicit characterizations of FPTIME and NC revisited
• On the computational complexity of imperative programming languages
• A characterization of alternating log time by ramified recurrence
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• A Characterization of NC k by First Order Functional Programs
• scientific article; zbMATH DE number 176199 (Why is no real title available?)
• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• Pointers in recursion: exploring the tropics
• A Characterization of Alternating Log Time by First Order Functional Programs
• Constant time parallel computations in \(\lambda\)-calculus
• On parallel hierarchies and R ki
• Computation models and function algebras
• Characterizing parallel time by type 2 recursions with polynomial output length

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332666)