Independence Results about Context-Free Languages and Lower Bounds

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.