{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:05Z","timestamp":1725483725829},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_28","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"323-332","source":"Crossref","is-referenced-by-count":1,"title":["Subtractive Reductions and Complete Problems for Counting Complexity Classes"],"prefix":"10.1007","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"28_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/3-540-48242-3_2","volume-title":"Proc. 6th LPAR","author":"M. Hermann","year":"1999","unstructured":"M. Hermann, L. Juban, and P. G. Kolaitis. On the complexity of counting the Hilbert basis of a linear Diophantine system. In Proc. 6th LPAR, volume 1705 of LNCS (in AI), pages 13\u201332, September 1999. Springer."},{"key":"28_CR2","first-page":"107","volume":"46","author":"L. A. Hemachandra","year":"1992","unstructured":"L. A. Hemachandra and M. Ogiwara. Is #P closed under subtraction? Bulletin of the EATCS, 46:107\u2013122, February 1992.","journal-title":"Bulletin of the EATCS"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L. A. Hemaspaandra","year":"1995","unstructured":"L. A. 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":"28_CR4","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF00276023","volume":"264","author":"J. K\u00f6bler","year":"1989","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. On counting and approximation. Acta Informatica, 26(4):363\u2013379, 1989.","journal-title":"Acta Informatica"},{"issue":"1-2","key":"28_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"J. McCarthy. Circumscription-A form of non-monotonic reasoning. Artficial Intelligence, 13(1-2):27\u201339, 1980.","journal-title":"Artficial Intelligence"},{"issue":"3","key":"28_CR6","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.A. Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Science, 46(3):295\u2013325, 1993.","journal-title":"Journal of Computer and System Science"},{"key":"28_CR7","unstructured":"A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1986."},{"key":"28_CR8","series-title":"PhD thesis","volume-title":"Computational complexity of counting complexity classes","author":"S. Toda","year":"1991","unstructured":"S. Toda. Computational complexity of counting complexity classes. PhD thesis, Tokyo Institute of Technology, Dept. of Computer Science, Tokyo, 1991."},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"S. Toda and O. Watanabe. Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science, 100(1):205\u2013221, 1992.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"28_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"28_CR11","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"28_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3(1):23\u201333, 1976.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T03:35:59Z","timestamp":1707881759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}