We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira's system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) the $${\Sigma^b_{\infty}}$$ definable functions of $${\mathbb{A}({\sf PHCA})}$$ a...
AbstractNew proofs of two properties of the polynomial-time hierarchy are given. The classes in the ...
Colloque avec actes et comité de lecture. internationale.International audienceThis paper presents a...
AbstractWe consider the relation between the relativized polynomial time hierarchy and relativizatio...
In this paper we study (self-)applicative theories of operations and binary words in the context of ...
AbstractSeveral authors have independently introduced second order theories whose provably total fun...
We present theories of bounded arithmetic and weak analysis whose provably total functions (with ap...
AbstractWe introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time...
This paper introduces a more restrictive notion of feasibility of functionals on Baire space than th...
AbstractThe bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hiera...
We show that if a complexity class C is closed downward under polynomialtime majority truth-table re...
We introduce multifunction algebras Bτ i where τ is a set of 0 or 1-ary terms used to bound recursio...
A partial combinatory algebra (PCA) is a model of computation that embodies a certain notion of algo...
AbstractLet PLω be the provability logic of IΔ0 + ω1. We prove some containments of the form L⊆PLω⊥h...
An account of Valiant's theory of p-computable versus p-definable polynomials, an arithmetic analogu...
Just as P = NP if and only if some NP-complete set ; is a member of P, the class NP is closed unde...
AbstractNew proofs of two properties of the polynomial-time hierarchy are given. The classes in the ...
Colloque avec actes et comité de lecture. internationale.International audienceThis paper presents a...
AbstractWe consider the relation between the relativized polynomial time hierarchy and relativizatio...
In this paper we study (self-)applicative theories of operations and binary words in the context of ...
AbstractSeveral authors have independently introduced second order theories whose provably total fun...
We present theories of bounded arithmetic and weak analysis whose provably total functions (with ap...
AbstractWe introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time...
This paper introduces a more restrictive notion of feasibility of functionals on Baire space than th...
AbstractThe bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hiera...
We show that if a complexity class C is closed downward under polynomialtime majority truth-table re...
We introduce multifunction algebras Bτ i where τ is a set of 0 or 1-ary terms used to bound recursio...
A partial combinatory algebra (PCA) is a model of computation that embodies a certain notion of algo...
AbstractLet PLω be the provability logic of IΔ0 + ω1. We prove some containments of the form L⊆PLω⊥h...
An account of Valiant's theory of p-computable versus p-definable polynomials, an arithmetic analogu...
Just as P = NP if and only if some NP-complete set ; is a member of P, the class NP is closed unde...
AbstractNew proofs of two properties of the polynomial-time hierarchy are given. The classes in the ...
Colloque avec actes et comité de lecture. internationale.International audienceThis paper presents a...
AbstractWe consider the relation between the relativized polynomial time hierarchy and relativizatio...