{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:55:03Z","timestamp":1725573303735},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_35","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"368-379","source":"Crossref","is-referenced-by-count":0,"title":["Universal Relations and #P-Completeness"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Malod","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Biswas, S.: Universal relations. In: Structure in Complexity Theory Conference, pp. 207\u2013220 (1992)","DOI":"10.1109\/SCT.1992.215395"},{"key":"35_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural complexity 1","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural complexity 1. Springer, New York (1988)"},{"issue":"2","key":"35_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphisms and density of NP and other complete sets. SIAM J. Comput.\u00a06(2), 305\u2013322 (1977)","journal-title":"SIAM J. Comput."},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Kadin, J., Thierauf, T.: On functions computable with nonadaptive queries to NP. In: Structure in Complexity Theory Conference, pp. 43\u201352 (1994)","DOI":"10.1109\/SCT.1994.315819"},{"key":"35_CR5","unstructured":"Chakravorty, G., Kumar, R.: #P universality. Technical report, Indian Institute of Technology (2003)"},{"key":"35_CR6","unstructured":"Chaudhary, V., Sinha, A.K., Biswas, S.: Universality for nondeterministic logspace. In: Presented at Indo-German Workshop on Algorithms, Bangalore (2004)"},{"key":"35_CR7","volume-title":"Computational complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley Publishing Company, Reading (1994)"},{"key":"35_CR8","unstructured":"Poizat, B.: Les Petits Caillloux. Nur Al-Mantiq Wal-Ma\u2019rifah, vol.\u00a03. Al\u00e9as, Lyon (1995)"},{"issue":"1-2","key":"35_CR9","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(97)00029-7","volume":"201","author":"N. Portier","year":"1998","unstructured":"Portier, N.: R\u00e9solutions universelles pour des probl\u00e8mes NP-complets. Theor. Comput. Sci.\u00a0201(1-2), 137\u2013150 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"35_CR10","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.\u00a020(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"35_CR11","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:29Z","timestamp":1619507069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11758471_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}