JEDNOSTKA NAUKOWA KATEGORII A+

Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

Truth definition for $\Delta _ 0$ formulas and PSPACE computations

Tom 252 / 2021

Konrad Zdanowski Fundamenta Mathematicae 252 (2021), 1-38 MSC: 03F30, 03F35, 68Q15. DOI: 10.4064/fm578-1-2020 Opublikowany online: 3 July 2020

Streszczenie

One of the long-standing open problems in bounded arithmetic is whether there exists a truth definition for bounded formulas which does not use the exponentiation function. We relate the existence of a sufficiently good truth definition for bounded formulas in a given theory $T$ to the representation of $\textrm {PSPACE}$ computations. Also, we show that an extension of Buss’s theory $S^1_2$ with such a truth definition admits a $\textrm {PSPACE}$ witnessing theorem.

Autorzy

  • Konrad ZdanowskiFaculty of Mathematics and Natural Sciences
    Cardinal Stefan Wyszyński University in Warsaw
    Wóycickiego 1/3
    01-938 Warszawa, Poland
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek