Witnessing functions in bounded arithmetic and search problems

Publisher： Cambridge University Press

E-ISSN： 1943-5886|63|3|1095-1115

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.63, Iss.3, 1998-09, pp. : 1095-1115

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We investigate the possibility to characterize (multi)functions that are -definable with small i (i = 1, 2, 3) in fragments of bounded arithmetic T 2 in terms of natural search problems defined over polynomial-time structures. We obtain the following results:

Related content

NP search problems in low fragments of bounded arithmetic

By  

The Journal of Symbolic Logic, Vol. 72, Iss. 2, 2007-06 ,pp. : 649-672 (24)

Cambridge University Press

Access to resources Recommend Favorite

Provably total functions of intuitionistic bounded arithmetic

By  

The Journal of Symbolic Logic, Vol. 57, Iss. 2, 1992-06 ,pp. : 466-477 (12)

Cambridge University Press

Access to resources Recommend Favorite

Gödel sentences of bounded arithmetic

By  

The Journal of Symbolic Logic, Vol. 65, Iss. 3, 2000-09 ,pp. : 1338-1346 (9)

Cambridge University Press

Access to resources Recommend Favorite

Forcing on bounded arithmetic II

By  

The Journal of Symbolic Logic, Vol. 63, Iss. 3, 1998-09 ,pp. : 860-868 (9)

Cambridge University Press

Access to resources Recommend Favorite

Notes on polynomially bounded arithmetic

By  

The Journal of Symbolic Logic, Vol. 61, Iss. 3, 1996-09 ,pp. : 942-966 (25)

Cambridge University Press

Access to resources Recommend Favorite