Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Independence Results in Computer Science

Independence Results in Computer Science

File(s)
76-296.ps (153.9 KB)
76-296.pdf (509.9 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6063
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
Hopcroft, John E.
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^{*}$.

Date Issued
1976-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-296
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance