Polynomial and Abstract Subrecursive Classes

We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial classes are generated by running time. They posses a modified Ritchie-Cobham property. A polynomial class is a complexity class iff it is honest.

Authors

• Kurt Mehlhorn

Keywords

No keywords are indexed for this paper.