Independence results about context-free languages and lower bounds

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 representation 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 context-free language L₀ such that for no cf-grammar G, L(G) = L₀, it is provable in F that “L(G) is not regular”. We also show, among other results about P and NP, that there exists a recursive oracle A such that NP^A ≠ 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 nondeterministic 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.