Showing 1–3 of 3 results for author: Oitavem, I

Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories

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

Abstract: We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language) precisely capture polytime random functions. Then, we provide two new characterizations of the semantic class BPP obtained by internalizing the error-bound check within a logical system: the first relies on measure-sens… ▽ More We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language) precisely capture polytime random functions. Then, we provide two new characterizations of the semantic class BPP obtained by internalizing the error-bound check within a logical system: the first relies on measure-sensitive quantifiers, while the second is based on standard first-order quantification. This leads us to introduce a family of effectively enumerable subclasses of BPP, called BPP_T and consisting of languages captured by those probabilistic Turing machines whose underlying error can be proved bounded in the theory T. As a paradigmatic example of this approach, we establish that polynomial identity testing is in BPP_T where T=$\mathrm{I}Δ_0+\mathrm{Exp}$ is a well-studied theory based on bounded induction. △ Less

Submitted 25 November, 2023; originally announced November 2023.

ACM Class: F.4.1; F.1.3

An Arithmetic Theory for the Poly-Time Random Functions

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

Abstract: 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, called POR, together with the theory of arithmetic RS^1_2. Then, we show that functions computed by poly-time PTMs are arithmetically characterized b… ▽ More 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, called POR, together with the theory of arithmetic RS^1_2. Then, we show that functions computed by poly-time PTMs are arithmetically characterized by a class of probabilistic bounded formulas. △ Less

Submitted 6 February, 2023; v1 submitted 27 January, 2023; originally announced January 2023.

Comments: 37 pages, pre-print

An applicative theory for FPH

Authors: Reinhard Kahle, Isabel Oitavem

Abstract: In this paper we introduce an applicative theory which characterizes the polynomial hierarchy of time. In this paper we introduce an applicative theory which characterizes the polynomial hierarchy of time. △ Less

Submitted 27 January, 2011; originally announced January 2011.

Comments: In Proceedings CL&C 2010, arXiv:1101.5200

ACM Class: F.4.1; F.1.3

Journal ref: EPTCS 47, 2011, pp. 44-56