Function-algebraic characterizations of log and polylog parallel time (Q1332666)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Function-algebraic characterizations of log and polylog parallel time |
scientific article |
Statements
Function-algebraic characterizations of log and polylog parallel time (English)
0 references
1 September 1994
0 references
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.
0 references
computational complexity classes
0 references
0 references
