Polynomial time operations in explicit mathematics
Journal of Symbolic Logic 62 (2):575-594 (1997)
| Abstract | In this paper we study (self)-applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on W = {0, 1} * are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesAndreas Blass & Yuri Gurevich (2003). Strong Extension Axioms and Shelah's Zero-One Law for Choiceless Polynomial Time. Journal of Symbolic Logic 68 (1):65-131.
Kazushige Terui (2004). Light Affine Set Theory: A Naive Set Theory of Polynomial Time. Studia Logica 77 (1):9 - 40.
Stephen A. Fenner, Stuart A. Kurtz & James S. Royer (2004). Every Polynomial-Time 1-Degree Collapses If and Only If P = Pspace. Journal of Symbolic Logic 69 (3):713-741.
Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Yuri Gurevich & Saharon Shelah (1989). Time Polynomial in Input or Output. Journal of Symbolic Logic 54 (3):1083-1088.
Andreas Blass, Yuri Gurevich & Saharon Shelah (2002). On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic 67 (3):1093-1125.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,651 of 549,068 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
