{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:14Z","timestamp":1750309094718,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[1977,2,1]],"date-time":"1977-02-01T00:00:00Z","timestamp":223603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[1977,2]]},"abstract":"<jats:p>In recent work [12][13], Plaisted has considered the computational complexity of certain decision problems for sparse polynomials. The present expository paper is intended to make these results accessible to those working in the area of algebraic manipulation and to clarify the relevance of the results to this area. The basic insight to be gained is that if the best known algorithms for a problem concerning (not necessarily sparse) polynomials process sparse polynomials in such a way that sparsity is lost, then one should not expect it to be possible to design special algorithms with consistently improved performance on sparse polynomials, unless one hopes to solve the NP = P problem positively. Also we note, for the sake of improved communication between complexity theorists and those working on algebraic manipulation, that there is a significant difference between the conventions used for expressing computation time in the two areas: Many algorithms which always run within a polynomial number of steps, in terms of the algebraic parameters involved, will require an exponential number of steps, in terms of input length (as is the usage in complexity theory), on infinitely many inputs.<\/jats:p>","DOI":"10.1145\/1088233.1088236","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"8-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The impact of complexity theory on algorithms for sparse polynomials"],"prefix":"10.1145","volume":"11","author":[{"given":"Kenneth L.","family":"Manders","sequence":"first","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1977,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803405"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_3_1","volume-title":"An Introduction to the Theory of Numbers","author":"Hardy G. H.","year":"1938","unstructured":"Hardy , G. H. and Wright , E. M. , An Introduction to the Theory of Numbers . Clarendon Press , 1938 ( 4 th ed., 1960). (Theorem 7) Hardy, G. H. and Wright, E. M., An Introduction to the Theory of Numbers. Clarendon Press, 1938 (4th ed., 1960). (Theorem 7)","edition":"4"},{"key":"e_1_2_1_4_1","volume-title":"Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity","author":"Johnson D. S.","year":"1976","unstructured":"Johnson , D. S. , Approximation algorithms for combinatorial problems: prospects and limitations . In Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity , 1976 . Johnson, D. S., Approximation algorithms for combinatorial problems: prospects and limitations. In Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity, 1976."},{"key":"e_1_2_1_5_1","volume-title":"Complexity of Computer Computation, eds. R. N. Miller and J. W. Thatcher","author":"Karp R. M.","year":"1972","unstructured":"Karp , R. M. , Reducibility among combinatorial problems . In Complexity of Computer Computation, eds. R. N. Miller and J. W. Thatcher , Plenum Press , 1972 , 85--104. Karp, R. M., Reducibility among combinatorial problems. In Complexity of Computer Computation, eds. R. N. Miller and J. W. Thatcher, Plenum Press, 1972, 85--104."},{"key":"e_1_2_1_6_1","volume-title":"Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity","author":"Karp R. M.","year":"1976","unstructured":"Karp , R. M. , The probabilistic analysis of some combinatorial search algorithms . In Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity , 1976 . Karp, R. M., The probabilistic analysis of some combinatorial search algorithms. In Proc. Carnegie-Mellon Symp. on New Directions and Recent Results in Algorithms and Complexity, 1976."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_8_1","first-page":"115","article-title":"Universal sorting problems (Russian)","author":"Levin P. A.","year":"1973","unstructured":"Levin , P. A. , Universal sorting problems (Russian) . Problemi Peredaci Informacii IX ( 1973 ) 115 -- 116 . Levin, P. A., Universal sorting problems (Russian). Problemi Peredaci Informacii IX (1973) 115--116.","journal-title":"Problemi Peredaci Informacii"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803627"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803773"},{"key":"e_1_2_1_11_1","volume-title":"Finite and Infinite Machines","author":"Minsky M. L.","year":"1967","unstructured":"Minsky , M. L. , Computation : Finite and Infinite Machines , Prentice-Hall , 1967 . Minsky, M. L., Computation: Finite and Infinite Machines, Prentice-Hall, 1967."},{"key":"e_1_2_1_12_1","unstructured":"Plaisted D. A. Sparse complex polynomials and polynomial reducibility. To appear in JCSS.  Plaisted D. A. Sparse complex polynomials and polynomial reducibility. To appear in JCSS."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.29"},{"key":"e_1_2_1_14_1","volume-title":"Carus Monograph Series No. 9, M.A.A. (dist","author":"Pollard H.","year":"1950","unstructured":"Pollard , H. , The Theory of Algebraic Numbers , Carus Monograph Series No. 9, M.A.A. (dist . J. Wiley) , 1950 . Pollard, H., The Theory of Algebraic Numbers, Carus Monograph Series No. 9, M.A.A. (dist. J. Wiley), 1950."},{"key":"e_1_2_1_15_1","unstructured":"Pratt V. Succinct certificates for primes. To appear.  Pratt V. Succinct certificates for primes. To appear."},{"key":"e_1_2_1_16_1","unstructured":"Read R. C. and Corneil D. G. The graph isomorphism disease. To appear in J. Graph Theory.  Read R. C. and Corneil D. G. The graph isomorphism disease. To appear in J. Graph Theory ."},{"key":"e_1_2_1_17_1","volume-title":"West Coast Number Theory Conf.","author":"Shanks D., A","year":"1975","unstructured":"Shanks , D., A new method of factorization of O(N1\/4) . West Coast Number Theory Conf. , December 1975 . Shanks, D., A new method of factorization of O(N1\/4). West Coast Number Theory Conf., December 1975."},{"key":"e_1_2_1_18_1","unstructured":"Tarjan R. Private communication.  Tarjan R. Private communication."},{"key":"e_1_2_1_19_1","first-page":"42","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"2","author":"Turing A. M.","year":"1936","unstructured":"Turing , A. M. , On computable numbers, with an application to the Entscheidungsproblem . Proc. Lond. Math. Soc. Ser. 2 42 ( 1936 ), 230--265. Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. Ser. 2 42 (1936), 230--265.","journal-title":"Proc. Lond. Math. Soc. Ser."},{"key":"e_1_2_1_20_1","volume-title":"West Coast Number Theory Conf.","author":"Wunderlich M. C.","year":"1975","unstructured":"Wunderlich , M. C. , How fast is the Brillhart-Morrison method of factorisation ? West Coast Number Theory Conf. , December 1975 . Wunderlich, M. C., How fast is the Brillhart-Morrison method of factorisation? West Coast Number Theory Conf., December 1975."}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1088233.1088236","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1088233.1088236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:44Z","timestamp":1750286624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1088233.1088236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,2]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1977,2]]}},"alternative-id":["10.1145\/1088233.1088236"],"URL":"https:\/\/doi.org\/10.1145\/1088233.1088236","relation":{},"ISSN":["0163-5824"],"issn-type":[{"type":"print","value":"0163-5824"}],"subject":[],"published":{"date-parts":[[1977,2]]},"assertion":[{"value":"1977-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}