{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:17Z","timestamp":1725549497768},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_20","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T08:40:30Z","timestamp":1268383230000},"page":"237-249","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Hilbert\u2019s 17th Problem"],"prefix":"10.1007","author":[{"given":"Nikhil R.","family":"Devanur","sequence":"first","affiliation":[]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[]},{"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pp. 2\u201313 (1992)","DOI":"10.1109\/SFCS.1992.267824"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/BF02952513","volume":"5","author":"E. Artin","year":"1927","unstructured":"Artin, E.: \u00dcber die Zerlegung definiter Funktionen in Quadrate. Abh. Math. Sem. Univ. Hamburg\u00a05, 100\u2013115 (1927)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"20_CR4","unstructured":"Blekherman, G.: There are significantly more non-negative polynomials than sums of squares. (preprint)"},{"key":"20_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real algebraic geometry","author":"H. Bochnak","year":"1998","unstructured":"Bochnak, H., Coste, M., Roy, M.-F.: Real algebraic geometry. Springer, Heidelberg (1998)"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"Boppana, R., Hastad, J., Zachos, S.: Does Co-NP Have Short Interactive Proofs? Information Processing Letters\u00a025, 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Browder, F. (ed.): Mathematical developments arising from Hilbert\u2019s Problems. In: Proc. Symp. Pure Math, vol.\u00a028. Amer. Math. Soc, providence (1976)","DOI":"10.1090\/pspum\/028.2"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1515\/crll.1982.336.45","volume":"336","author":"M.D. Choi","year":"1982","unstructured":"Choi, M.D., Dai, Z.D., Lam, T.Y., Reznick, B.: The pythagoras number of some affine algebras and local algebras. J. Reine Angew. Math.\u00a0336, 45\u201382 (1982)","journal-title":"J. Reine Angew. Math."},{"key":"20_CR9","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"},{"key":"20_CR10","first-page":"540","volume-title":"Bull","author":"D.W. Dubois","year":"1967","unstructured":"Dubois, D.W.: Note on of Hilbert\u2019s 17th problem. In: Bull, vol.\u00a073, pp. 540\u2013541. Amer. Math. Soc, providence (1967)"},{"key":"20_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/BF01443605","volume":"32","author":"D. Hilbert","year":"1888","unstructured":"Hilbert, D.: \u00dcber die Darstellung definiter Formen als Summen von Formenquadraten. Math. Ann.\u00a032, 342\u2013350 (1888)","journal-title":"Math. Ann."},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02391990","volume":"17","author":"D. Hilbert","year":"1893","unstructured":"Hilbert, D.: \u00dcber tern\u00e4re definite Formen. Acta Math\u00a017, 169\u2013198 (1893)","journal-title":"Acta Math"},{"key":"20_CR14","unstructured":"Hilbert, D.: Grundlagen der Geometrie. Leipzig, ch. 7 (1899)"},{"key":"20_CR15","unstructured":"Hilbert, D.: Darstellung definiter Formen durch Quadrate. Akad. Wiss. G\u00f6ttingen, 284\u2013285 (1900)"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O.H. Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs. JACM\u00a030(1), 217\u2013228 (1983)","journal-title":"JACM"},{"issue":"1","key":"20_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/42267.45069","volume":"35","author":"E. Kaltofen","year":"1988","unstructured":"Kaltofen, E.: Greatest common divisors of polynomials given by straight-line programs. JACM\u00a035(1), 231\u2013264 (1988)","journal-title":"JACM"},{"key":"20_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.M. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, NewYork (1972)"},{"issue":"3","key":"20_CR19","first-page":"265","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: Universal\u2019nye perebornye zadachi (Universal search problems: in Russian). Problemy Peredachi Informatsii\u00a09(3), 265\u2013266 (1973)","journal-title":"Problemy Peredachi Informatsii"},{"key":"20_CR20","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01425382","volume":"4","author":"A. Pfister","year":"1967","unstructured":"Pfister, A.: Zur Darstellung definiter Funktionen als Summe von Quadraten. Invent. Math.\u00a04, 229\u2013237 (1967)","journal-title":"Invent. Math."},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0022-4049(00)00155-9","volume":"164","author":"V. Powers","year":"2001","unstructured":"Powers, V., Reznick, B.: A new bound for Po\u2018lya\u2019s Theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Alg.\u00a0164, 221\u2013229 (2001)","journal-title":"J. Pure Appl. Alg."},{"key":"20_CR23","series-title":"Monographs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04648-7","volume-title":"Positive Polynomials: From Hilbert\u2019s 17th Problem to Real Algebra","author":"A. Prestel","year":"2001","unstructured":"Prestel, A., Delzell, C.N.: Positive Polynomials: From Hilbert\u2019s 17th Problem to Real Algebra. Monographs in Mathematics. Springer, Heidelberg (2001)"},{"key":"20_CR24","unstructured":"Reznick, B.: Some concrete aspects of Hilbert\u2019s 17th Problem. Publ. Math. Univ. Paris VII\u00a056 (January 1996)"},{"key":"20_CR25","unstructured":"Reznick, B.: On the absence of uniform denominators in Hilbert\u2019s Seventeenth Problem.(preprint)"},{"key":"20_CR26","unstructured":"Roy, M.-F.: The role of Hilbert\u2019s problems in real algebraic geometry. In: Proceedings of the ninth EWM Meeting, Loccum, Germany (1999)"},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01362149","volume":"207","author":"G. Stengle","year":"1974","unstructured":"Stengle, G.: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann.\u00a0207, 87\u201397 (1974)","journal-title":"Math. Ann."},{"key":"20_CR28","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"Strassen, V.: Vermiedung von Divisionen. J. Reine Angew. Math\u00a0264, 184\u2013202 (1973)","journal-title":"J. Reine Angew. Math"},{"issue":"1","key":"20_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/3072340","volume":"110","author":"R. Thiele","year":"2003","unstructured":"Thiele, R.: Hilbert\u2019s Twenty-Fourth Problem. American Math. Monthly\u00a0110(1), 1\u201323 (2003)","journal-title":"American Math. Monthly"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:58:47Z","timestamp":1605743927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}