Time polynomial in input or output

&
Journal of Symbolic Logic 54 (3):1083-1088 (1989)
  Copy   BIBTEX

Abstract

We introduce the class PIO of functions computable in time that is polynomial in max{the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings

Categories

Keywords

Reprint years

DOI

10.2307/2274767

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Computing mechanisms.Gualtiero Piccinini - 2007 - Philosophy of Science 74 (4):501-526.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
On polynomial time computation over unordered structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Eliminating definitions and Skolem functions.Jeremy Avigad - unknown
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Eliminating definitions and Skolem functions in first-order logic.Jeremy Avigad - manuscript
Proving theorems of the second order Lambek calculus in polynomial time.Erik Aarts - 1994 - Studia Logica 53 (3):373 - 387.

Analytics

Added to PP
2009-01-28

Downloads
22 (#707,407)

6 months
7 (#425,099)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references