Polynomial and Abstract Subrecursive Classes

Mehlhorn, Kurt

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Polynomial and Abstract Subrecursive Classes

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Mehlhorn, K. (1974). Polynomial and Abstract Subrecursive Classes. In Conference Record of Sixth Annual ACM Symposium on Theory of computing (STOC-74) (pp. 96-109). New York, NY, USA: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AFE3-2

Abstract

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. Starting from the observation that many results about subrecursive classes hold for all reducibility relations (e.g. primitive recursive in, elementary recursive in), which were studied so far, we define abstract subrecursive reducibility relation. Many results hold for all abstract subrecursive reducibilities.