{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:42:25Z","timestamp":1725745345313},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_48","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"540-550","source":"Crossref","is-referenced-by-count":0,"title":["Length-Increasing Reductions for PSPACE-Completeness"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity, pp. 139\u2013147. IEEE Computer Society (2002)"},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, L., Manders, K.: Reducibility, randomness, and intractability. In: Proceedings of the 9th ACM Symposium on Theory of Computing, pp. 151\u2013163 (1977)","DOI":"10.1145\/800105.803405"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Watanabe, O.: One-way functions and the isomorphism conjecture. Technical Report TR09-019, Electronic Colloquium on Computational Complexity (2009)","DOI":"10.1109\/CCC.2009.17"},{"key":"48_CR4","unstructured":"Berman, L.: Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University (1977)"},{"issue":"2","key":"48_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing\u00a06(2), 305\u2013322 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"48_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00224-008-9163-5","volume":"47","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Hescott, B., Homer, S., Torenvliet, L.: Non-uniform reductions. Theory of Computing Systems\u00a047(2), 317\u2013341 (2010)","journal-title":"Theory of Computing Systems"},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third ACM Symposium on the Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"4","key":"48_CR8","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0221044","volume":"21","author":"K. Ganesan","year":"1992","unstructured":"Ganesan, K., Homer, S.: Complete problems and strong polynomial reducibilities. SIAM Journal on Computing\u00a021(4), 733\u2013742 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"48_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/s00224-011-9365-0","volume":"51","author":"X. Gu","year":"2012","unstructured":"Gu, X., Hitchcock, J.M., Pavan, A.: Collapsing and separating complete notions under worst-case and average-case hypotheses. Theory of Computing Systems\u00a051(2), 248\u2013265 (2012)","journal-title":"Theory of Computing Systems"},{"issue":"5","key":"48_CR10","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1016\/j.ic.2006.10.005","volume":"205","author":"J.M. Hitchcock","year":"2007","unstructured":"Hitchcock, J.M., Pavan, A.: Comparing reductions to NP-complete sets. Information and Computation\u00a0205(5), 694\u2013706 (2007)","journal-title":"Information and Computation"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013104. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"5","key":"48_CR13","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing\u00a031(5), 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:11:25Z","timestamp":1558303885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}