__
TR02-051 | 16th July 2002 00:00
__

#### Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

**Abstract:**
The use of Nepomnjascij's Theorem in the proofs of independence results

for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here S_1 is a conservative extension of the well-studied theory IDelta_0 and TLS is a theory whose Delta^b_{1,2}-predicates are precisely LOGSPACE. The relation of TLS from this paper to previously studied theories is also developed and generalizations of the previous two results to quasi-linear settings are discussed as well.