J. Hartmanis
J. E. Hopcroft
Skip Abstract Section
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) = Σ* or L(G) ≠ Σ*.
- Aho, A. V., J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms," Addison-Wesley Publishing Co., Reading, Mass., 1974. Google Scholar
Digital Library
- Baker, T., J. Gill and R. Solovay, "Relativizations of the P = ?NP Question," SIAM J. on Comp. 4:4 (1975), pp. 431--442.Google ScholarCross Ref
- Bernays, P., and A. A. Fraenkel, "Axiomatic Set Theory," North Holland Publ., Amsterdam, 1958.Google Scholar
- Blum, M., "A machine-independent theory of recursive functions," JACM 14:2 (1964), pp. 322--336. Google ScholarDigital Library
- Hartmanis, J. and J. Simon, "On the structure of feasible computations" in Advances in Computers Vol. 14 (Edits. Morris Rubinoff and Marshall C. Yovits), Academic Press, New York, N.Y., 1976. pp. 1--43.Google Scholar
- Hopcroft, J. E. and J. D. Ullman, "Formal Languages and Their Relation to Automata," Addison-Wesley, Reading, Mass., 1969. Google ScholarDigital Library
- Matijasevic, Y. "Enumerable sets are Diophantine" (Russian), Dokl. Acad. Nauk. SSSR 191 (1970), pp. 279--282.Google Scholar
- Rogers, Hartly, Jr., "Theory of Recursive Functions and Effective Computability," McGraw-Hill, New York, N.Y., 1967. Google ScholarDigital Library
Index Terms
- Independence results in computer science
Index terms have been assigned to the content through auto-classification.
Recommendations
Impossibility results on weakly black-box hardness amplification
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation TheoryWe study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower ...
Comments