A Simple Observation Regarding Iterations Of Finite-valued Polynomial-time Functions

Reports on Mathematical Logic:19-29 (2009)
  Copy   BIBTEX

Abstract

We present this note to point out that the finite-valued polynomial-time computable functions are closed with respect to iteration. This fact is not a difficult result, however it can be useful in constructions not exceeding the class of polynomial-time computable functions.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,642

External links

  • This entry has no external links. Add one.
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

Predicatively computable functions on sets.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (3-4):471-485.
Polynomial time ultrapowers and the consistency of circuit lower bounds.Jan Bydžovský & Moritz Müller - 2020 - Archive for Mathematical Logic 59 (1-2):127-147.
Bounded iteration and unary functions.Stefano Mazzanti - 2005 - Mathematical Logic Quarterly 51 (1):89-94.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Time polynomial in input or output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
On the complexity of finding paths in a two‐dimensional domain I: Shortest paths.Arthur W. Chou & Ker-I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.
A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
On the complexity of finding paths in a two-dimensional domain I: Shortest paths.Arthur W. Chou & Ker-I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.
Cancellation laws for polynomial-time p-isolated sets.John N. Crossley & J. B. Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):147-172.

Analytics

Added to PP
2015-02-12

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references