Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Mehlhorn, Kurt

dblp



Editor(s):





BibTeX cite key*:

mehlhorn74a

Title, Booktitle

Title*:

Polynomial and Abstract Subrecursive Classes


Mehlhorn_a_1974_a.pdf (682.58 KB)

Booktitle*:

Conference Record of Sixth Annual ACM Symposium on Theory of computing (STOC-74)

Event, URLs

URL of the conference:


URL for downloading the paper:

http://delivery.acm.org/10.1145/810000/803890/p96-mehlhorn.pdf?key1=803890&key2=3858822611&coll=GUIDE&dl=GUIDE&CFID=3463240&CFTOKEN=85811342

Event Address*:

Seattle, Washington, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

30 April 1974

Event End Date:

2 May 1974

Publisher

Name*:

ACM

URL:


Address*:

New York, NY, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

96-109

Year*:

1974

VG Wort Pages:


ISBN/ISSN:

--

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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.

URL for the Abstract:

http://doi.acm.org/10.1145/800119.803890
http://portal.acm.org/citation.cfm?id=800119.803890#



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{mehlhorn74a,
AUTHOR = {Mehlhorn, Kurt},
TITLE = {Polynomial and Abstract Subrecursive Classes},
BOOKTITLE = {Conference Record of Sixth Annual ACM Symposium on Theory of computing (STOC-74)},
JOURNAL = {Informatik Spektrum},
PUBLISHER = {ACM},
YEAR = {1974},
PAGES = {96--109},
ADDRESS = {Seattle, Washington, USA},
ISBN = {--},
}


Entry last modified by Christine Kiesel, 11/09/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
08/07/2006 06:58:25 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
09.11.2006 16:13:14
31.10.2006 11:56:25
31.10.2006 11:53:14
08.08.2006 13:52:15
07.08.2006 15:33:50
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_1974_a.pdf
View attachments here: