ECCC-Report TR02-051https://eccc.weizmann.ac.il/report/2002/051Comments and Revisions published for TR02-051en-usThu, 05 Sep 2002 20:09:23 +0300
Paper TR02-051
| Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic |
Chris Pollett
https://eccc.weizmann.ac.il/report/2002/051The 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.
Thu, 05 Sep 2002 20:09:23 +0300https://eccc.weizmann.ac.il/report/2002/051