eCommons

 

Independence Results about Context-Free Languages and Lower Bounds

Other Titles

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 Lo such that for no cf-grammar G,L(G)=Lo, 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 NPAPA, 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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1984-05

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-606

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record