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 in Computer Science
Authors: Hartmanis, Juris
Hopcroft, John E.
Keywords: computer science
technical report
Issue Date: Dec-1976
Publisher: Cornell University
Abstract: In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the famous P = NP problem cannot be answered in formalized set theory, that explicit algorithms can be given whose running time is independent of the axioms of set theory, and that one can exhibit a specific context-free grammar G for which it cannot be proven in set theory that $L(G) = \sum^{\*}$ or $L(G) \neq \sum^{\*}$.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
76-296.pdf509.9 kBAdobe PDFView/Open
76-296.ps153.9 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us