Portugaliae Mathematica   EMIS ELibM Electronic Journals PORTUGALIAE
Vol. 63, No. 4, pp. 427-450 (2006)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



An interpretation of ${\sf S}^1_2$ in $\Sigma^b_1{\sf -NIA}$

Gilda Ferreira and Isabel Oitavem

CMAF -- Universidade de Lisboa,
1649-003 Lisboa -- PORTUGAL
E-mail: gildafer@cii.fc.ul.pt
Dept. Matemática da FCT-UNL and CMAF-UL,
E-mail: isarocha@ptmat.fc.ul.pt

Abstract: In this paper the theory ${\sf S}^1_2$ (of Buss) is interpreted in the theory $\Sigma^b_1{\sf -NIA}$ (of Ferreira).

Keywords: bounded arithmetic; interpretability; polynomial time.

Classification (MSC2000): 03F30, 03F25, 03D20.

Full text of the article:

Electronic version published on: 7 Mar 2008.

© 2006 Sociedade Portuguesa de Matemática
© 2006–2008 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition