CrossRef Open Access 2003

A theory for Log-Space and NLIN versus co-NLIN

Chris Pollett

Abstrak

AbstractThe use of Nepomnjaščiǐ's Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, it is shown that at least one ofS1orTLSdoes not prove the Matiyasevich-Robinson-Davis-Putnam Theorem. It is also established thatTLSdoes not prove a statement that roughly means nondeterministic linear time is equal to co-nondeterministic linear time. HereS1is a conservative extension of the well-studied theoryIΔ0andTLSis a theory for LOGSPACE reasoning.

Penulis (1)

Chris Pollett

Format Sitasi

APA MLA BibTeX

Pollett, C. (2003). A theory for Log-Space and NLIN versus co-NLIN. https://doi.org/10.2178/jsl/1067620174

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.2178/jsl/1067620174

Informasi Jurnal

Tahun Terbit: 2003
Bahasa: en
Sumber Database: CrossRef
DOI: 10.2178/jsl/1067620174
Akses: Open Access ✓