A carregar...
Projeto de investigação
Strategic Project - UI 209 - 2011-2012
Financiador
Autores
Publicações
Techniques in weak analysis for conservation results
Publication . Fernandes, António; Ferreira, Fernando; Ferreira, Gilda
We review and describe the main techniques for setting up systems of weak
analysis, i.e. formal systems of second-order arithmetic related to subexponential
classes of computational complexity. These involve techniques of proof theory
(e.g., Herbrand’s theorem and the cut-elimination theorem) and model theoretic
techniques like forcing. The techniques are illustrated for the particular case of
polytime computability. We also include a brief section where we list the known
results in weak analysis.
Interpretability in Robinson's Q
Publication . Ferreira, Fernando; Ferreira, Gilda
Edward Nelson published in 1986 a book defending an extreme formalist view of
mathematics according to which there is an impassable barrier in the totality of exponentiation.
On the positive side, Nelson embarks on a program of investigating how much mathematics can
be interpreted in Raphael Robinson’s theory of arithmetic Q. In the shadow of this program,
some very nice logical investigations and results were produced by a number of people, not only
regarding what can be interpreted in Q but also what cannot be so interpreted. We explain some
of these results and rely on them to discuss Nelson’s position.
Bounded theories for polyspace computability
Publication . Bianconi, Ricardo; Ferreira, Gilda; Silva, Emmanuel
We present theories of bounded arithmetic and weak analysis whose provably total functions
(with appropriate graphs) are the polyspace computable functions. More precisely, inspired in
Ferreira’s systems PTCA, Sigma^b_1-NIA and BTFA in the polytime framework, we propose analogue theories
concerning polyspace computability. Since the techniques we employ in the characterization of
PSPACE via formal systems (e.g. Herbrand’s theorem, cut-elimination theorem and the expansion
of models) are similar to the ones involved in the polytime setting, we focus on what is specific of
polyspace and explains the lift from PTIME to PSPACE.
Unidades organizacionais
Descrição
Palavras-chave
Contribuidores
Financiadores
Entidade financiadora
Fundação para a Ciência e a Tecnologia
Programa de financiamento
6817 - DCRRNI ID
Número da atribuição
PEst-OE/MAT/UI0209/2011