{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:51:40Z","timestamp":1742914300920,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354666"},{"type":"electronic","value":"9783540354680"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780342_47","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T02:19:46Z","timestamp":1151461186000},"page":"459-470","source":"Crossref","is-referenced-by-count":3,"title":["Fast Quantifier Elimination Means P = NP"],"prefix":"10.1007","author":[{"given":"Mihai","family":"Prunescu","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"publisher","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.: Complexity and real computation. Springer, New York (1998)"},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation of complexity over the real numbers. American Mathematical Society Bulletin 21 (1989)","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"47_CR3","unstructured":"Ga\u00dfner, C.: A structure of finite signature with identity relation and with P = NP. Preprints of the University Greifswald number 1, 2, 13, 14 \/2004; 1, 9, 17 \/ 2005; 1 \/ 2006 (different versions and expositions)"},{"issue":"4","key":"47_CR4","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.jco.2005.02.001","volume":"21","author":"A. Hemmerling","year":"2005","unstructured":"Hemmerling, A.: P = NP for some structures over the binary words. Journal of Complexity\u00a021(4), 557\u2013578 (2005)","journal-title":"Journal of Complexity"},{"issue":"19","key":"47_CR5","doi-asserted-by":"publisher","first-page":"690","DOI":"10.2307\/2024634","volume":"72","author":"S. Kripke","year":"1975","unstructured":"Kripke, S.: Outline of a theory of truth. The Journal of Philosophy\u00a072(19), 690\u2013716 (1975)","journal-title":"The Journal of Philosophy"},{"key":"47_CR6","unstructured":"Poizat, B.: Les petits cailloux. ALEAS, Lyon (1995)"},{"key":"47_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-44622-2_4","volume-title":"Computer Science Logic","author":"B. Poizat","year":"2000","unstructured":"Poizat, B.: Une tentative malheureuse de construire une structure \u00e9liminant rapidement les quanteurs. In: Clote, P.G., Schwichtenberg, H. (eds.) CSL 2000. LNCS, vol.\u00a01862, pp. 61\u201370. Springer, Heidelberg (2000)"},{"issue":"4","key":"47_CR8","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1002\/1521-3870(200111)47:4<557::AID-MALQ557>3.0.CO;2-O","volume":"47","author":"M. Prunescu","year":"2001","unstructured":"Prunescu, M.: Non-effective quantifier elimination. Mathematical Logic Quarterly\u00a047(4), 557\u2013561 (2001)","journal-title":"Mathematical Logic Quarterly"},{"issue":"1","key":"47_CR9","doi-asserted-by":"publisher","first-page":"321","DOI":"10.2178\/jsl\/1140641177","volume":"71","author":"M. Prunescu","year":"2006","unstructured":"Prunescu, M.: Structure with fast elimination of quantifiers. The Journal of Symbolic Logic\u00a071(1), 321\u2013328 (2006)","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Logical Approaches to Computational Barriers"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780342_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T13:00:35Z","timestamp":1555678835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780342_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354666","9783540354680"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/11780342_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}