Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Independence Results about Context-Free Languages and Lower Bounds
Authors: Hartmanis, Juris
Keywords: computer science
technical report
Issue Date: May-1984
Publisher: Cornell University
Abstract: We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free 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 non-regular context-free language $L_{o}$ such that for no cf-grammar $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 (p-isomorphisms) of NP complete sets. We show that for every NP complete set, L, there is a representation of L by a non-deterministic polynomial time machine for which we can prove that L is NP complete. Furthermore if L is p-isomorphic 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 p-isomorphic 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 p-isomorphic to SAT.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
84-606.pdf1.05 MBAdobe PDFView/Open
84-606.ps267.88 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us