English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Polynomial and Abstract Subrecursive Classes

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AFE3-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AFE4-F
Genre: Conference Paper

Files

show Files
hide Files
:
Mehlhorn_a_1974_a.pdf (Any fulltext), 683KB
 
File Permalink:
-
Name:
Mehlhorn_a_1974_a.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Mehlhorn, Kurt1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2006-11-091974
 Publication Status: Issued
 Pages: -
 Publishing info: New York, NY, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 344667
Other: Local-ID: C1256428004B93B8-63A954F1A9EEB61AC12571C3001B5234-mehlhorn74a
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Seattle, Washington, USA
Start-/End Date: 1974-04-30

Legal Case

show

Project information

show

Source 1

show
hide
Title: Conference Record of Sixth Annual ACM Symposium on Theory of computing (STOC-74)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, NY, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 96 - 109 Identifier: ISBN: --