2002 · 69 citations · 14 references
ComputingComputer ScienceComputational LinguisticsProgramming LanguagesTheory Of ComputationComputational ComplexityComputational Complexity ClassesFunctional ProgrammingRecursion TheoryType CheckingType SystemsCategory Theory For Programming LanguagesComplexityLambda CalculusLambda Calculus SemanticsOracle ComputationPolynomial Time ComplexityType TheoryTyped Lambda Calculus
We present a higher-order functional notation for polynomial-time computation with an arbitrary 0, 1-valued oracle. This formulation provides a linguistic characterization for classes such as NP and BPP, as well as a notation for probabilistic polynomial-time functions. The language is derived from Hofmann's adaptation of Bellantoni-Cook safe recursion, extended to oracle computation via work derived from that of Kapron and Cook. Like Hofmann's language, ours is an applied typed lambda calculus with complexity bounds enforced by a type system. The type system uses a modal operator to distinguish between two sorts of numerical expressions. Recursion can take place on only one of these sorts. The proof that the language captures precisely oracle polynomial time is model-theoretic, using adaptations of various techniques from category theory.
14
J. H. van Lint · 2020 · 4.5K citations
Jean-Yves Girard · Theoretical Computer Science · 1987 · 4.1K citations
Introduction to the Theory of Computation
Michael Sipser · ACM SIGACT News · 1996 · 2.8K citations
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
A calculus for cryptographic protocols
Martı́n Abadi, Andrew D. Gordon · 1997 · 1.2K citations · Full text