{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:54Z","timestamp":1725663174453},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_73","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:58:13Z","timestamp":1330203493000},"page":"259-269","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial-time functions generate SAT: On P-splinters"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemachandra","sequence":"first","affiliation":[]},{"given":"Albrecht","family":"Hoene","sequence":"additional","affiliation":[]},{"given":"Dirk","family":"Siefkes","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"21_CR1","unstructured":"M. Abadi, E. Allender, A. Broder, J. Feigenbaum, and L. Hemachandra. On generating solved instances of computational problems. To appear in Proceedings of CRYPTO 1988."},{"issue":"2","key":"21_CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6(2):305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"J. Cai and L. Hemachandra. On the power of parity polynomial time. In STACS 1989: 6th Annual Symposium on Theoretical Aspects of Computer Science, pages 229\u2013239. Springer-Verlag Lecture Notes in Computer Science #349, 1989.","DOI":"10.1007\/BFb0028987"},{"key":"21_CR4","series-title":"Technical Report","volume-title":"Neartestable sets","author":"J. Goldsmith","year":"1987","unstructured":"J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young. Neartestable sets. Technical Report 87-11-06, University of Washington, Department of Computer Science, Seattle, Washington, November 1987. Submitted for publication."},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"J. Goldsmith and D. Joseph. Three results on the polynomial isomorphism of complete sets. In Proceedings 27th IEEE Symposium on Foundations of Computer Science, pages 390\u2013397, 1986.","DOI":"10.1109\/SFCS.1986.56"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"J. Goldsmith, D. Joseph, and P. Young. Self-reducible, P-selective, near-testable, and P-cheatable sets: The effect of internal structure on the complexity of a set. In Proceedings 2nd Structure in Complexity Theory Conference, pages 50\u201359, 1987.","DOI":"10.1109\/PSCT.1987.10319254"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"S4 Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. In 17th ACM Symposium on Theory of Computing, pages 291\u2013304, April 1985.","DOI":"10.1145\/22145.22178"},{"key":"21_CR8","volume-title":"Polynomial Isomorphisms and Near-Testable Sets","author":"J. Goldsmith","year":"1989","unstructured":"J. Goldsmith. Polynomial Isomorphisms and Near-Testable Sets. PhD thesis, University of Wisconsin-Madison, Madison, WI, January 1989. Available as Technical Report 816."},{"key":"21_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L. Goldschlager","year":"1986","unstructured":"L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions. Theoretical Computer Science, 43:43\u201358, 1986.","journal-title":"Theoretical Computer Science"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"J. Hartmanis and L. Hemachandra. One-way functions, robustness, and the non-isomorphism of NP-complete sets. In Proceedings 2nd Structure in Complexity Theory Conference, pages 160\u2013174. IEEE Computer Society Press, June 1987.","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"21_CR11","series-title":"Technical Report","volume-title":"Polynomial-time functions generate SAT: On P-splinters","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra, A. Hoene, and D. Siefkes. Polynomial-time functions generate SAT: On P-splinters. Technical Report TR-276, University of Rochester, Department of Computer Science, Rochester, NY, 14627, March 1989."},{"key":"21_CR12","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"issue":"23","key":"21_CR13","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43(2,3):169\u2013188, 1986.","journal-title":"Theoretical Computer Science"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(85)90140-9","volume":"39","author":"D. Joseph","year":"1985","unstructured":"D. Joseph and P. Young. Some remarks on witness functions for non-polynomial and non-complete sets in NP. Theoretical Computer Science, 39:225\u2013237, 1985.","journal-title":"Theoretical Computer Science"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. Collapsing degrees. In Proceedings 27th IEEE Symposium on Foundations of Computer Science, pages 380\u2013389, 1986.","DOI":"10.1109\/SFCS.1986.13"},{"key":"21_CR16","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, S. Toda, and J. Tor\u00e1n. Turing machines with few accepting computations and low sets for PP. In Proceedings 4th Structure in Complexity Theory Conference. IEEE Computer Society Press. To appear."},{"key":"21_CR17","series-title":"Technical Report","volume-title":"A relativized failure of the Berman-Hartmanis conjecture","author":"S. Kurtz","year":"1983","unstructured":"S. Kurtz. A relativized failure of the Berman-Hartmanis conjecture. Technical Report TR83-001, University of Chicago Department of Computer Science, Chicago, IL, 1983."},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22:155\u2013171, 1975.","journal-title":"Journal of the ACM"},{"key":"21_CR19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(85)90139-2","volume":"39","author":"S. Mahaney","year":"1985","unstructured":"S. Mahaney and P. Young. Reductions among polynomial isomorphism types. Theoretical Computer Science, 39:207\u2013224, 1985.","journal-title":"Theoretical Computer Science"},{"key":"21_CR20","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01342904","volume":"138","author":"J. Myhill","year":"1959","unstructured":"J. Myhill. Recursive digraphs, splinters, and cylinders. Mathematische Annalen, 138:211\u2013218, 1959.","journal-title":"Mathematische Annalen"},{"key":"21_CR21","unstructured":"M. Pilchner, R. Rardin, and C. Tovey. Polynomial constructibility and traveling salesman problems of intermediate complexity. Technical Report ONR-URI Computational Combinatorics Report CC-88-2, Purdue University, 1988."},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag Lecture Notes in Computer Science #145, 1983.","DOI":"10.1007\/BFb0009651"},{"key":"21_CR23","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R. Rivest","year":"1978","unstructured":"R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signature and public-key cryptosystems. Communications of the ACM, 21:120\u2013126, 1978.","journal-title":"Communications of the ACM"},{"key":"21_CR24","series-title":"Technical Report","volume-title":"On language instance constructors and generators","author":"L. Sanchis","year":"1988","unstructured":"L. Sanchis. On language instance constructors and generators. Technical Report TR-260, University of Rochester, Department of Computer Science, Rochester, NY, 14627, September 1988."},{"key":"21_CR25","unstructured":"L. Sanchis. Test case construction for NP-hard problems. In 26th Annual Allerton Conference on Communication, Control, and Computing, September 1988."},{"key":"21_CR26","series-title":"Technical Report","volume-title":"Efficient language instance generation","author":"L. Sanchis","year":"1988","unstructured":"L. Sanchis and M. Fulk. Efficient language instance generation. Technical Report TR-235, University of Rochester, Department of Computer Science, Rochester, NY, 14627, January 1988."},{"key":"21_CR27","volume-title":"Structural Properties of the Counting Hierarchies","author":"J. Tor\u00e1n","year":"1988","unstructured":"J. Tor\u00e1n. Structural Properties of the Counting Hierarchies. PhD thesis, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain, 1988."},{"key":"21_CR28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.2307\/2964335","volume":"25","author":"J. Ullian","year":"1960","unstructured":"J. Ullian. Splinters of recursive functions. Journal of Symbolic Logic, 25:33\u201338, 1960.","journal-title":"Journal of Symbolic Logic"},{"key":"21_CR29","doi-asserted-by":"crossref","first-page":"70","DOI":"10.2307\/2270621","volume":"31","author":"P. Young","year":"1966","unstructured":"P. Young. Linear orderings under one-one reducibility. Journal of Symbolic Logic, 31:70\u201385, 1966.","journal-title":"Journal of Symbolic Logic"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"P. Young. Some structural properties of polynomial reducibilities and sets in NP. In 15th ACM Symposium on Theory of Computing, pages 392\u2013401, April 1983.","DOI":"10.1145\/800061.808770"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T13:18:34Z","timestamp":1713619114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}