A theory for Log-Space and NLIN versus co-NLIN
Chris Pollett · Journal of Symbolic Logic · 2003
Abstract The 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.