An interpretation of S12 in Σ b1-NIA

Isabel Oitavem, Gilda Ferreira

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper the theory S12 (of Buss) is interpreted in the theory Σb1−NIA (of Ferreira).
Original languageEnglish
Pages (from-to)427-450
Number of pages24
JournalPortugaliae Mathematica
Volume63
Issue number4
Publication statusPublished - 26 Jan 2006

Keywords

  • bounded arithmetic
  • interpretability
  • polynomial time

Cite this