{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:51:08Z","timestamp":1787507468533,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540569923","type":"print"},{"value":"9783540478904","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56992-8_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:00:25Z","timestamp":1330239625000},"page":"43-60","source":"Crossref","is-referenced-by-count":6,"title":["Optimization problems: Expressibility, approximation properties and expected asymptotic growth of optimal solutions"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Behrendt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Compton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erich","family":"Gr\u00e4del","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"5_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1991","unstructured":"N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York (1991)."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and in-tractability of approximation problems, Proceedings of Annual IEEE Symposium on Foundations of Computer Science (1992), 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"A. Blass and Y. Gurevich, Existential fixed-point logic, in: \u201cComputation Theory and Logic\u201d (E. B\u00f6rger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 20\u201336.","DOI":"10.1007\/3-540-18170-9_151"},{"key":"5_CR4","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random graphs, Academic Press, London (1985)."},{"key":"5_CR5","first-page":"353","volume-title":"NATO Advanced Study Institute on algorithms and Order","author":"K. Compton","year":"1988","unstructured":"K. Compton, 0\u20131 laws in logic and combinatorics, in: \u201cNATO Advanced Study Institute on algorithms and Order\u201d, (I. Rival, Ed), pp 353\u2013383, Reidel, Dordrecht (1988)."},{"key":"5_CR6","first-page":"43","volume-title":"Complexity of Computations, SIAM-AMS Proc. 7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized first-order spectra and polynomial time recognizable sets, Complexity of Computations, SIAM-AMS Proc. 7 (1974), Richard Karp, ed., American Math. Soc., Providence, RI, 43\u201373."},{"key":"5_CR7","volume-title":"Computers and Intractibility: A Guide the to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide the to the Theory of NP-Completeness, Freeman, New York (1979)."},{"key":"5_CR8","unstructured":"T. Hirst and D. Harel, Taking it to the Limit: On Infinite Variants of NP-Complete Problems, unpublished manuscript (1992)."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational Queries Computable in Polynomial Time, Information and Control 68 (1986), 86\u2013104.","journal-title":"Information and Control"},{"key":"5_CR10","volume-title":"Dissertation","author":"V. Kann","year":"1992","unstructured":"V. Kann, On the Approximability of NP-complete Optimization Problems, Dissertation (1992), Royal Institute of Technology, Stockholm."},{"key":"5_CR11","unstructured":"Ph. Kolaitis and M. Thakur, Logical definability of NP optimization problems, to appear in Information and Computation."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Thakur, Approximation properties of NP minimization classes, Proceedings of 6th IEEE Conference on Structure in Complexity Theory (1991), 353\u2013366, to appear in Journal of Computer and System Sciences.","DOI":"10.1109\/SCT.1991.160280"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Vardi, The decision problem for the probabilities of higher-order properties, Proceedings of 19th Annual ACM Symposium on Theory of Computing (1987), 425\u2013435.","DOI":"10.1145\/28395.28441"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. Kolaitis","year":"1992","unstructured":"Ph. Kolaitis and M. Vardi, Infinitary logic and 0\u20131 laws, Information and Computation 98 (1992), 258\u2013294.","journal-title":"Information and Computation"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"C. Lautemann, Logical definability of NP-optimization problems with monadic auxiliary predicates, Informatik-Bericht Nr. 1\/92, Institut f\u00fcr Informatik, Johannes Gutenberg-Universit\u00e4t Mainz (1992).","DOI":"10.1007\/3-540-56992-8_19"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"A. Panconesi and D. Ranjan, Quantifiers and approximation, Proceedings of 22nd Annual ACM Symposium on Theory of Computing (1990), 446\u2013456.","DOI":"10.1145\/100216.100275"},{"key":"5_CR17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Ch. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity, Journal of Computer and System Sciences 43 (1991), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR18","unstructured":"Ch. Papadimitriou and M. Yannakakis, On the complexity of computing the V-C dimension, Extended Abstract (1992)."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of Relational Query Languages, Proc. of 14th Annual ACM Symposium on Theory of Computing (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56992-8_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T00:10:54Z","timestamp":1640909454000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56992-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569923","9783540478904"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-56992-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}