{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:49:08Z","timestamp":1725468548586},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055791","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"418-426","source":"Crossref","is-referenced-by-count":0,"title":["A second step towards circuit complexity-theoretic analogs of Rice's theorem"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-16486-3_85","volume":"223","author":"E. Allender","year":"1986","unstructured":"E. Allender. The complexity of sparse sets in P. In Proceedings of the 1st Structure in Complexity Theory Conference, pages 1\u201311. Springer-Verlag Lecture Notes in Computer Science #223, June 1986.","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"issue":"6","key":"38_CR2","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E. Allender","year":"1988","unstructured":"E. Allender and R. Rubinstein. P-printable sets. SIAM Journal on Computing, 17(6): 1193\u20131202, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"R. Beigel. On the relativized power of additional accepting paths. In Proceedings of the 4th Structure in Complexity Theory Conference, pages 216\u2013224. IEEE Computer Society Press, June 1989.","DOI":"10.1109\/SCT.1989.41827"},{"key":"38_CR4","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-63385-5_37","volume":"1289","author":"B. Borchert","year":"1997","unstructured":"B. Borchert and F. Stephan. Looking for an analogue of Rice's Theorem in circuit complexity theory. In Proceedings on the 1997 Kurt G\u00f6del Colloquium, pages 114\u2013127. Springer-Verlag Lecture Notes in Computer Science #1289, 1997.","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"issue":"6","key":"38_CR5","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232\u20131252, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"38_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95\u2013111, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"38_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02090768","volume":"23","author":"J. Cai","year":"1990","unstructured":"J. Cai and L. Hemachandra. On the power of parity polynomial time. Mathematical Systems Theory, 23(2):95\u2013106, 1990.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"38_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1): 116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81\u2013107. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_4"},{"key":"38_CR10","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"issue":"2","key":"38_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"38_CR12","first-page":"395","volume":"6","author":"T. Gundermann","year":"1987","unstructured":"T. Gundermann and G. Wechsung. Counting classes with finite acceptance types. Computers and Artificial Intelligence, 6(5):395\u2013409, 1987.","journal-title":"Computers and Artificial Intelligence"},{"issue":"1","key":"38_CR13","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0022-0000(71)80007-7","volume":"5","author":"J. Hartmanis","year":"1971","unstructured":"J. Hartmanis and F. Lewis. The use of lists in the study of undecidable problems in automata theory. Journal of Computer and System Sciences, 5(1):54\u201366, 1971.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR14","volume-title":"Technical Report TR-662","author":"L. Hemaspaandra","year":"1997","unstructured":"L. Hemaspaandra and J. Rothe. Complexity-theoretic analogs of Rice's Theorem. Technical Report TR-662, Department of Computer Science, University of Rochester, Rochester, NY, July 1997."},{"issue":"1","key":"38_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and H. Vollmer. The Satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News, 26(1):2\u201313, 1995.","journal-title":"SIGACT News"},{"key":"38_CR16","volume-title":"Technical Report TR-480","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra and M. Zimand. Strong forms of balanced immunity. Technical Report TR-480, Department of Computer Science, University of Rochester, Rochester, NY, December 1993. Revised May, 1994."},{"issue":"2","key":"38_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-3975(94)90041-8","volume":"127","author":"J. Kari","year":"1994","unstructured":"J. Kari. Rice's Theorem for the limit sets of cellular automata. Theoretical Computer Science, 127(2):229\u2013254, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"38_CR18","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/0022-0000(92)90022-B","volume":"44","author":"J. K\u00f6bler","year":"1992","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, S. Toda, and J. Tor\u00e1n. Turing machines with few accepting computations and low sets for PP. Journal of Computer and System Sciences, 44(2):272\u2013286, 1992.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"38_CR19","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. Hemachandra. A complexity theory for closure properties. Journal of Computer and System Sciences, 46(3):295\u2013325, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR20","doi-asserted-by":"publisher","first-page":"358","DOI":"10.2307\/1990888","volume":"74","author":"H. Rice","year":"1953","unstructured":"H. Rice. Classes of recursively enumerable sets and their decision problems. Transactions of the AMS, 74:358\u2013366, 1953.","journal-title":"Transactions of the AMS"},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"304","DOI":"10.2307\/2269105","volume":"21","author":"H. Rice","year":"1956","unstructured":"H. Rice. On completely recursively enumerable classes and their key arrays. Journal of Symbolic Logic, 21:304\u2013341, 1956.","journal-title":"Journal of Symbolic Logic"},{"key":"38_CR22","volume-title":"PhD thesis","author":"S. Toda","year":"1991","unstructured":"S. Toda. Computational Complexity of Counting Complexity Classes. PhD thesis, Department of Computer Science, Tokyo Institute of Technology, Tokyo, Japan, 1991."},{"issue":"1","key":"38_CR23","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluating. Information Processing Letters, 5(1):20\u201323, 1976.","journal-title":"Information Processing Letters"},{"issue":"3","key":"38_CR24","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR25","volume-title":"PhD thesis","author":"H. Vollmer","year":"1994","unstructured":"H. Vollmer. Komplexit\u00e4tsklassen von Funktionen. PhD thesis, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany, 1994."},{"key":"38_CR26","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(88)90071-3","volume":"27","author":"O. Watanabe","year":"1988","unstructured":"O. Watanabe. On hardness of one-way functions. Information Processing Letters, 27:151\u2013157, 1988.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T18:25:52Z","timestamp":1549909552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0055791","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}