Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6063
 Title: Independence Results in Computer Science Authors: Hartmanis, JurisHopcroft, John E. Keywords: computer sciencetechnical report Issue Date: Dec-1976 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-296 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^{\*}$. URI: http://hdl.handle.net/1813/6063 Appears in Collections: Computer Science Technical ReportsHartmanis, Juris

Files in This Item:

File Description SizeFormat