Independence Results about Context-Free Languages and Lower Bounds
No Access Until
Permanent Link(s)
Other Titles
Author(s)
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