{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:04Z","timestamp":1742617084633,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:15:43Z","timestamp":1330254943000},"page":"484-493","source":"Crossref","is-referenced-by-count":0,"title":["Gap-definability as a closure property"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Fermer","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"Lide","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"R. Beigel, J. Gill, and U. Hertrampf. Counting classes: Thresholds, parity, mods, and fewness. In Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science, pages 49\u201357, 1990.","DOI":"10.1007\/3-540-52282-4_31"},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. In Proc. of the 23rd ACM Symp. on the Theory of Computing, pages 1\u20139, 1991.","DOI":"10.1145\/103418.103426"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. In Proc. of the 6th Structure in Complexity Theory Conf., pages 30\u201342, 1991.","DOI":"10.1109\/SCT.1991.160241"},{"key":"48_CR4","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic complexity classes. SIAM Journal on Computing, 6:675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"F. Green, J. K\u00f6bler, and J. Tor\u00e1n. The power of the middle bit. In Proceedings of the 7th Structure in Complexity Theory Conf., pages 111\u2013117, 1992.","DOI":"10.1109\/SCT.1992.215386"},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. Graph isomorphism is low for PP. In Proc. of the 9th Symp. on Theoretical Aspects of Computer Science, 1992.","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"48_CR7","unstructured":"K. Regan and T. Schwentick On the power of one bit of a #P function. To appear in Proc. of the 4th Italian Conf. in Theoretical Comp. Sci., 1992."},{"key":"48_CR8","unstructured":"J. Simon. On some central problems in computational complexity. Technical Report TR75-224, Cornell University Department of Computer Science, 1975."},{"issue":"5","key":"48_CR9","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865\u2013877, 1991.","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"48_CR10","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. on Computing, 21(2):316\u2013328, 1992.","journal-title":"SIAM J. on Computing"},{"key":"48_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"48_CR12","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23:325\u2013356, 1986.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:49:19Z","timestamp":1742593759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}