Polynomial time over the reals with parsimony

Emmanuel Hainry (1) , Damiano Mazza (2) , Romain Péchoux (1)

1 MOCQUA - Designing the Future of Computational Models
2 LIPN - Laboratoire d'Informatique de Paris-Nord

We provide a characterization of Ko's class of polynomial time computable functions over real numbers. This characterization holds for a stream based language using a parsimonious type discipline, a variant of propositional linear logic. We obtain a first characterization of polynomial time computations over the reals on a higher-order functional language using a linear/affine type system.

Domaines: Complexité [cs.CC]; Informatique et langage [cs.CL]

Emmanuel Hainry, Damiano Mazza, Romain Péchoux. Polynomial time over the reals with parsimony. FLOPS 2020 - International Symposium on Functional and Logic Programming, Apr 2020, Akita, Japan. ⟨hal-02499149⟩