An Arithmetic Theory for the Poly-Time Random Functions

Autor: Antonelli, Melissa, Lago, Ugo Dal, Davoli, Davide, Oitavem, Isabel, Pistone, Paolo

We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time. Concretely, we pass through a class of oracle functions over string,

Externí odkaz: http://arxiv.org/abs/2301.12028

An applicative theory for FPH

Autor: Kahle, Reinhard, Oitavem, Isabel

Publikováno v: EPTCS 47, 2011, pp. 44-56

In this paper we introduce an applicative theory which characterizes the polynomial hierarchy of time.
Comment: In Proceedings CL&C 2010, arXiv:1101.5200

Externí odkaz: http://arxiv.org/abs/1101.5444

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

A Recursion-Theoretic Characterization of the Probabilistic Class PP

Autor: Dal Lago, Ugo, Kahle, Reinhard, Oitavem, Isabel

Publikováno v: Proceedings of MFCS 2021
MFCS 2021-46th International Symposium on Mathematical Foundations of Computer Science
MFCS 2021-46th International Symposium on Mathematical Foundations of Computer Science, Aug 2021, Tallinn, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.35⟩
Proceedings of MFCS 2021,46th International Symposium on Mathematical Foundations of Computer Science

Probabilistic complexity classes, despite capturing the notion of feasibility, have escaped any treatment by the tools of so-called implicit-complexity. Their inherently semantic nature is of course a barrier to the characterization of classes like B

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9fd446f1cf3bb8c6ab9ab5686ad93a12
https://inria.hal.science/hal-03346791/file/mfcs2021.pdf

A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions

Autor: Das, Anupam, Oitavem, Isabel

Publikováno v: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

We extend work of Lautemann, Schwentick and Stewart [Clemens Lautemann et al., 1996] on characterisations of the "positive" polynomial-time predicates (posP, also called mP by Grigni and Sipser [Grigni and Sipser, 1992]) to function classes. Our main

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aa446e5811c16848fe0d824b18a3590f