{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T03:58:28Z","timestamp":1768276708336,"version":"3.49.0"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[1976,10,1]],"date-time":"1976-10-01T00:00:00Z","timestamp":212976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[1976,10]]},"abstract":"<jats:p>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) = \u03a3* or L(G) \u2260 \u03a3*.<\/jats:p>","DOI":"10.1145\/1008335.1008336","type":"journal-article","created":{"date-parts":[[2004,10,12]],"date-time":"2004-10-12T15:20:46Z","timestamp":1097594446000},"page":"13-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Independence results in computer science"],"prefix":"10.1145","volume":"8","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, N.Y."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. E.","family":"Hopcroft","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, N.Y."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1976,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Mass.","author":"Aho A. V.","year":"1974","unstructured":"Aho , A. V. , J. E. Hopcroft and J. D. Ullman , The Design and Analysis of Computer Algorithms,\" Addison-Wesley Publishing Co., Reading , Mass. , 1974 . Aho, A. V., J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms,\" Addison-Wesley Publishing Co., Reading, Mass., 1974."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_3_1","volume-title":"Axiomatic Set Theory,\" North Holland Publ","author":"Bernays P.","year":"1958","unstructured":"Bernays , P. , and A. A. Fraenkel , \" Axiomatic Set Theory,\" North Holland Publ ., Amsterdam , 1958 . Bernays, P., and A. A. Fraenkel, \"Axiomatic Set Theory,\" North Holland Publ., Amsterdam, 1958."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"e_1_2_1_5_1","first-page":"1","volume-title":"On the structure of feasible computations\" in Advances in Computers","author":"Hartmanis J.","year":"1976","unstructured":"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 . 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."},{"key":"e_1_2_1_6_1","volume-title":"Mass.","author":"Hopcroft J. E.","year":"1969","unstructured":"Hopcroft , J. E. and J. D. Ullman , \" Formal Languages and Their Relation to Automata,\" Addison-Wesley, Reading , Mass. , 1969 . Hopcroft, J. E. and J. D. Ullman, \"Formal Languages and Their Relation to Automata,\" Addison-Wesley, Reading, Mass., 1969."},{"key":"e_1_2_1_7_1","first-page":"279","article-title":"Enumerable sets are Diophantine","volume":"191","author":"Matijasevic Y.","year":"1970","unstructured":"Matijasevic , Y. \" Enumerable sets are Diophantine \" (Russian), Dokl. Acad. Nauk. SSSR 191 ( 1970 ), pp. 279 -- 282 . Matijasevic, Y. \"Enumerable sets are Diophantine\" (Russian), Dokl. Acad. Nauk. SSSR 191 (1970), pp. 279--282.","journal-title":"(Russian), Dokl. Acad. Nauk. SSSR"},{"key":"e_1_2_1_8_1","unstructured":"Rogers Hartly Jr. \"Theory of Recursive Functions and Effective Computability \" McGraw-Hill New York N.Y. 1967.   Rogers Hartly Jr. \"Theory of Recursive Functions and Effective Computability \" McGraw-Hill New York N.Y. 1967."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008335.1008336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008335.1008336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:25:07Z","timestamp":1750263907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008335.1008336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,10]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1976,10]]}},"alternative-id":["10.1145\/1008335.1008336"],"URL":"https:\/\/doi.org\/10.1145\/1008335.1008336","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[1976,10]]},"assertion":[{"value":"1976-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}