A foundational delineation of poly-time
From MaRDI portal
Publication:1327386
DOI10.1006/inco.1994.1038zbMath0799.03042OpenAlexW2041616904MaRDI QIDQ1327386
Publication date: 19 June 1994
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1994.1038
polynomial timefeasibilityconstructive second- order logicdescriptional complexity theoryset-existence principles
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Light affine lambda calculus and polynomial time strong normalization, A refined interpretation of intuitionistic logic by means of atomic polymorphism, Intrinsic theories and computational complexity, Theories with self-application and computational complexity., Primitive recursive selection functions for existential assertions over abstract algebras, Light linear logic, A proof-theoretic characterization of the basic feasible functionals, Radical anti-realism, Wittgenstein and the length of proofs, A recursion-theoretic characterisation of the positive polynomial-time functions, A note on complexity measures for inductive classes in constructive type theory, Light linear logic, Linear logic by levels and bounded time complexity, A decidable characterization of the classes between lintime and exptime, Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity, On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
