Characterizing polynomial time complexity of stream programs using interpretations

Hugo Férée (1) , Emmanuel Hainry (1) , Mathieu Hoyrup (1) , Romain Péchoux (1)

1 CARTE - Theoretical adverse computations, and safety

This paper provides a criterion based on interpretation methods on term rewrite systems in order to characterize the polynomial time complexity of second order functionals. For that purpose it introduces a first order functional stream language that allows the programmer to implement second order functionals. This characterization is extended through the use of exp-poly interpretations as an attempt to capture the class of Basic Feasible Functionals (bff). Moreover, these results are adapted to provide a new characterization of polynomial time complexity in computable analysis. These characterizations give a new insight on the relations between the complexity of functional stream programs and the classes of functions computed by Oracle Turing Machine, where oracles are treated as inputs.

Mots clés: Rewriting; Type-2 Functionals; Stream Programs; Interpretations; Polynomial Time; Basic Feasible Functionals; Computable Analysis

Domaines: Complexité [cs.CC]

Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux. Characterizing polynomial time complexity of stream programs using interpretations. Theoretical Computer Science, 2015, 585, pp.41-54. ⟨10.1016/j.tcs.2015.03.008⟩. ⟨hal-01112160⟩