Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Polynomial and Abstract Subrecursive Classes

Polynomial and Abstract Subrecursive Classes

File(s)
74-198.pdf (1.31 MB)
74-198.ps (420.03 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6038
Collections
Computer Science Technical Reports
Author
Mehlhorn, Kurt
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 possess a modified Ritchie-Cobham property. A polynomial class is a complexity class if 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.

Date Issued
1974-02
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-198
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance