Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-051 | 16th July 2002 00:00

Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

RSS-Feed




TR02-051
Authors: Chris Pollett
Publication: 5th September 2002 20:09
Downloads: 842
Keywords: 


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.



ISSN 1433-8092 | Imprint