{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:22Z","timestamp":1725483742283},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_59","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"640-649","source":"Crossref","is-referenced-by-count":7,"title":["Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Steffen","family":"Reith","sequence":"first","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"59_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"N. Creignou and M. Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125:1\u201312, 1996.","journal-title":"Information and Computation"},{"issue":"6","key":"59_CR2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N. Creignou","year":"1997","unstructured":"N. Creignou and J.-J. H\u00e9brard. On generating all solutions of generalized satisfiability problems. Informatique Th\u00e9orique et Applications\/Theoretical Informatics and Applications, 31(6):499\u2013511, 1997.","journal-title":"Informatique Th\u00e9orique et Applications\/Theoretical Informatics and Applications"},{"doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Applied Mathematics. SIAM, 2000. To appear.","key":"59_CR3","DOI":"10.1137\/1.9780898718546"},{"key":"59_CR4","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51:511\u2013522, 1995.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"S. W. Jablonski, G. P. Gawrilow, and W. B. Kudrajawzew. Boolesche Funktionen und Postsche Klassen. Akademie-Verlag, 1970.","key":"59_CR5","DOI":"10.1515\/9783112649282"},{"unstructured":"L. Kirousis and P. G. Kolaitis. Dichotomy theorems for minimal satisfiability, manuscript, 1999.","key":"59_CR6"},{"key":"59_CR7","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. W. Krentel","year":"1988","unstructured":"M. W. Krentel. The complexity of optimization functions. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"59_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)90073-O","volume":"97","author":"M. W. Krentel","year":"1992","unstructured":"M. W. Krentel. Generalizations of OptP to the polynomial hierarchy. Theoretical Computer Science, 97:183\u2013198, 1992.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan, and L. Trevisan. Constraint satisfaction: The approximability of minimization problems. In Proceedings 12th Computational Complexity Conference, pages 282\u2013296. IEEE Computer Society Press, 1997.","key":"59_CR9","DOI":"10.1109\/CCC.1997.612323"},{"doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan, and D. Williamson. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. In Proceedings 29th Symposium on Theory of Computing, pages 11\u201320. ACM Press, 1997.","key":"59_CR10","DOI":"10.1145\/258533.258538"},{"key":"59_CR11","doi-asserted-by":"publisher","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":"59_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H. R. Lewis","year":"1979","unstructured":"Harry R. Lewis. Satisfiability problems for propositional calculi. Mathematical Systems Theory, 13:45\u201353, 1979.","journal-title":"Mathematical Systems Theory"},{"key":"59_CR13","series-title":"Annals of Mathematics Studies","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","author":"E. L. Post","year":"1941","unstructured":"E. L. Post. The Two-Valued Iterative Systems of Mathematical Logic. Annals of Mathematics Studies 5. Princeton University Press, London, 1941."},{"unstructured":"Steffen Reith and Klaus W. Wagner. The complexity of problems defined by boolean circuits. Technical Report 255, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 2000. To appear in Proceedings International Conference Mathematical Foundation of Informatics, Hanoi, October 25\u201328, 1999.","key":"59_CR14"},{"doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proccedings 10th Symposium on Theory of Computing, pages 216\u2013226. ACM Press, 1978.","key":"59_CR15","DOI":"10.1145\/800133.804350"},{"key":"59_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. W. Wagner","year":"1987","unstructured":"K. W. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science, 51:53\u201380, 1987.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T18:38:07Z","timestamp":1683830287000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/10.1007\/3-540-44612-5_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":16,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/3-540-44612-5_59","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}