eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6446
Title:  Independence Results about ContextFree Languages and Lower Bounds 
Authors:  Hartmanis, Juris 
Keywords:  computer science technical report 
Issue Date:  May1984 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84606 
Abstract:  We show that for any axiomatizable, sound formal system F there exist instances of natural problems about contextfree languages, lower bounds of computations and P versus NP that are not provable in F for any recursive representqation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the "opaqueness" of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a nonregular contextfree language $L_{o}$ such that for no cfgrammar $G, L(G) = L_{o}$, it is provable in F that "L(G) is not regular". We also show, among other results P and NP, that there exists a recursive oracle A such that $NP^{A} \neq P^{A}$, and that this fact is not provable in F for any recursive representation of A. The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (pisomorphisms) of NP complete sets. We show that for every NP complete set, L, there is a representation of L by a nondeterministic polynomial time machine for which we can prove that L is NP complete. Furthermore if L is pisomorphic to SAT then this is also provable in F for some representation of L. On the other hand, if there exist NP complete sets not pisomorphic to SAT then there exists an NP complete set L for which, independent of its representation, there is no proof in F that L is or is not pisomorphic to SAT. 
URI:  http://hdl.handle.net/1813/6446 
Appears in Collections:  Computer Science Technical Reports Hartmanis, Juris

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
