{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:04:50Z","timestamp":1743037490594,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":13,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_80","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:04:41Z","timestamp":1219662281000},"page":"447-451","source":"Crossref","is-referenced-by-count":1,"title":["Complexity Theory"],"prefix":"10.1007","author":[{"given":"Stephen A.","family":"Vavasis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"80_CR1_80","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"L. Blum","year":"1998","unstructured":"Blum L, Cucker F, Shub M, Smale S (1998) Complexity and real computation. Springer, Berlin"},{"key":"80_CR2_80","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1145\/800157.805047","volume-title":"Proc. 3rd Annual ACM Symp. Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook SA (1971) The complexity of theorem-proving procedures. In: Proc 3rd Annual ACM Symp Theory of Computing. ACM, pp 151\u2013158"},{"key":"80_CR3_80","volume-title":"Computers and intractability: A\u00a0guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: A\u00a0guide to the theory of NP-completeness. Freeman, New York"},{"key":"80_CR4_80","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2307\/1994208","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis J, Stearns RE (1965) On the computational complexity of algorithms. Trans Amer Math Soc 117:285\u2013306","journal-title":"Trans. Amer. Math. Soc."},{"key":"80_CR5_80","volume-title":"Introduction to automata theory, languages and computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft J, Ullman J (1979) Introduction to automata theory, languages and computation. Addison-Wesley, Reading, MA"},{"key":"80_CR6_80","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 RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of Computer Computations. Plenum, New York, pp 85\u2013103"},{"key":"80_CR7_80","volume-title":"Problem complexity and method efficiency in optimization","author":"A.S. Nemirovsky","year":"1983","unstructured":"Nemirovsky AS, Yudin DB (1983) Problem complexity and method efficiency in optimization. Wiley, New York"},{"key":"80_CR8_80","doi-asserted-by":"crossref","DOI":"10.1142\/2041","volume-title":"Complexity in numerical optimization","author":"P.M. Pardalos","year":"1993","unstructured":"Pardalos PM (1993) Complexity in numerical optimization. World Sci, Singapore"},{"key":"80_CR9_80","volume-title":"Information-based complexity","author":"J.F. Traub","year":"1988","unstructured":"Traub JF, Wasilkowski GW, Wo\u017aniakowski H (1988) Information\u2010based complexity. Acad Press, New York"},{"key":"80_CR10_80","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0167-6377(82)90047-5","volume":"1","author":"J.F. Traub","year":"1982","unstructured":"Traub JF, Wo\u017aniakowski H (1982) Complexity of linear programming. Oper Res Lett 1:59\u201362","journal-title":"Oper. Res. Lett."},{"key":"80_CR11_80","volume-title":"Nonlinear optimization: Complexity issues","author":"S.A. Vavasis","year":"1991","unstructured":"Vavasis SA (1991) Nonlinear optimization: Complexity issues. Oxford Univ. Press, Oxford"},{"key":"80_CR12_80","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0803004","volume":"3","author":"S.A. Vavasis","year":"1993","unstructured":"Vavasis SA (1993) Black-box complexity of local minimization. SIAM J Optim 3:60\u201380","journal-title":"SIAM J. Optim."},{"key":"80_CR13_80","first-page":"79","volume":"74","author":"S.A. Vavasis","year":"1996","unstructured":"Vavasis SA, Ye Y (1996) A\u00a0primal-dual interior point method whose running time depends only on the constraint matrix. Math Program 74:79\u2013120","journal-title":"Math. Program."}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_80","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T10:53:14Z","timestamp":1720695194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_80","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}