PORTUGALIAEMATHEMATICA
Vol. 63, No. 4, pp. 427-450 (2006)
|
|
PORTUGALIAE MATHEMATICA Vol. 63, No. 4, pp. 427-450 (2006) |
|
|
An interpretation of ${\sf S}^1_2$ in $\Sigma^b_1{\sf -NIA}$Gilda Ferreira and Isabel OitavemCMAF -- Universidade de Lisboa,1649-003 Lisboa -- PORTUGAL E-mail: gildafer@cii.fc.ul.pt Dept. Matemática da FCT-UNL and CMAF-UL, PORTUGAL 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
|