A new recursion-theoretic characterization of the polytime functions
From MaRDI portal
Publication:1207333
DOI10.1007/BF01201998zbMath0766.68037OpenAlexW2069792094MaRDI QIDQ1207333
Stephen A. Cook, Stephen J. Bellantoni
Publication date: 1 April 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01201998
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (only showing first 100 items - show all)
\textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs ⋮ How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study ⋮ A combination framework for complexity ⋮ Higher-order interpretations and program complexity ⋮ Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ Bounded combinatory logic and lower complexity ⋮ Function-algebraic characterizations of log and polylog parallel time ⋮ Reverse complexity ⋮ A new “feasible” arithmetic ⋮ A Short Introduction to Implicit Computational Complexity ⋮ Parsimonious Types and Non-uniform Computation ⋮ SAFE RECURSIVE SET FUNCTIONS ⋮ On efficiency of notations for natural numbers ⋮ A Categorical Setting for Lower Complexity ⋮ Simulation of simultaneous safe recursion over an arbitrary structure ⋮ On sharing, memoization, and polynomial time ⋮ A type-based complexity analysis of object oriented programs ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Algorithmically broad languages for polynomial time and space ⋮ Light affine lambda calculus and polynomial time strong normalization ⋮ Safe recursion revisited. I: Categorical semantics for lower complexity ⋮ Computational Complexity Via Finite Types ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Discrete Transfinite Computation ⋮ Analysing the implicit complexity of programs. ⋮ Linear types and non-size-increasing polynomial time computation. ⋮ Cobham recursive set functions ⋮ A recursion-theoretic approach to NP ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Theories with self-application and computational complexity. ⋮ The Power of Non-determinism in Higher-Order Implicit Complexity ⋮ Recursion Schemata for NC k ⋮ Continuous-time computation with restricted integration capabilities ⋮ An analysis of the Core-ML language: Expressive power and type reconstruction ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting) ⋮ A characterization of alternating log time by ramified recurrence ⋮ Soft linear set theory ⋮ Pointwise Transfinite Induction and a Miniaturized Predicativity ⋮ Type-two polynomial-time and restricted lookahead ⋮ Combining linear logic and size types for implicit complexity ⋮ An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ The Garland Measure and Computational Complexity of Stack Programs ⋮ A new recursion-theoretic characterization of the polytime functions ⋮ A survey of recursive analysis and Moore's notion of real computation ⋮ Quasi-interpretations. A way to control resources ⋮ Implicit complexity over an arbitrary structure: Quantifier alternations ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Control structures in programs and computational complexity ⋮ Elementary arithmetic ⋮ Structural recursion as a query language on lists and ordered trees ⋮ An arithmetic for polynomial-time computation ⋮ Resource control for synchronous cooperative threads ⋮ The computational SLR: a logic for reasoning about computational indistinguishability ⋮ Two algorithms in search of a type-system ⋮ Light types for polynomial time computation in lambda calculus ⋮ Tiering as a Recursion Technique ⋮ 2004 Summer Meeting of the Association for Symbolic Logic ⋮ Unnamed Item ⋮ A lexicographic path order with slow growing derivation bounds ⋮ Unary Resolution: Characterizing Ptime ⋮ 10th Asian Logic Conference ⋮ A Formalization of Polytime Functions ⋮ Dependency Pairs and Polynomial Path Orders ⋮ The Computational SLR: A Logic for Reasoning about Computational Indistinguishability ⋮ A note on complexity measures for inductive classes in constructive type theory ⋮ The polynomial hierarchy of functions and its levels ⋮ Complexity classes and fragments of C ⋮ Sequences, datalog, and transducers ⋮ A foundation for real recursive function theory ⋮ Separating NC along the \(\delta\) axis ⋮ Minimization and \(\mathbf{NP}\) multifunctions ⋮ On the computational complexity of imperative programming languages ⋮ On an interpretation of safe recursion in light affine logic ⋮ Feasible functionals and intersection of ramified types ⋮ Higher type recursion, ramification and polynomial time ⋮ Safe recursion with higher types and BCK-algebra ⋮ Implicit characterizations of FPTIME and NC revisited ⋮ Quantum implicit computational complexity ⋮ Linear logic by levels and bounded time complexity ⋮ Inductive definitions over a predicative arithmetic ⋮ A decidable characterization of the classes between lintime and exptime ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ A predicative and decidable characterization of the polynomial classes of languages ⋮ \({\mathcal M}^\omega\) considered as a programming language ⋮ Predicatively computable functions on sets ⋮ 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05 ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ An abstract approach to stratification in linear logic ⋮ Formal security proofs with minimal fuss: implicit computational complexity at work ⋮ A higher-order characterization of probabilistic polynomial time ⋮ A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Characterizing polynomial time complexity of stream programs using interpretations ⋮ Realizability models for a linear dependent PCF ⋮ Applicative theories for logarithmic complexity classes ⋮ Functions over free algebras definable in the simply typed lambda calculus ⋮ On the power of recursive word-functions without concatenation ⋮ Complexity of the search for the least solution to a system of dictionary equations of exponential type
Cites Work
This page was built for publication: A new recursion-theoretic characterization of the polytime functions
