Function-algebraic characterizations of log and polylog parallel time
type: Item
instance of: scholarly article
title: Function-algebraic characterizations of log and polylog parallel time
zbMATH Open document ID: 0813.68099
DOI: 10.1007/BF01202288
author: Stephen Bloch
published in: Computational Complexity
publication date: 1994-09-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 94C99
zbMATH DE Number: 627640
zbMATH Keywords: computational complexity classes
reviewed by: Du Ding-Zhu
MaRDI profile type: Publication
cites work: Arithmetizing uniform \(NC\)
cites work: A bounded arithmetic AID for Frege systems
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Q3140635
cites work: Bounded arithmetic for NC, ALogTIME, L and NL
cites work: An algebra and a logic for \(NC^ 1\)
cites work: Q4035315
cites work: On uniform circuit complexity
description: scientific article; zbMATH DE number 627640