{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:46Z","timestamp":1750220926054,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"crossref","award":["001 and PRINT"],"award-info":[{"award-number":["001 and PRINT"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Smale Institute"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition number, which is not assumed known by the machine. The theory admits deterministic and nondeterministic polynomial time recognizable problems. We prove that P is not NP in this theory if and only if P is not NP in the BSS theory over the reals.<\/jats:p>\n          <jats:p>Then we develop a theory with weak and strong approximate computations. This theory is intended to model actual numerical computations that are usually performed in floating point arithmetic. It admits classes P and NP and also an NP-complete problem. We relate the P vs. NP question in this new theory to the classical P vs. NP problem.<\/jats:p>","DOI":"10.1145\/3321479","type":"journal-article","created":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T12:23:16Z","timestamp":1559564596000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8456-3959","authenticated-orcid":false,"given":"Gregorio","family":"Malajovich","sequence":"first","affiliation":[{"name":"Universidade Federal do Rio de Janeiro, Rio de Janeiro RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Shub","sequence":"additional","affiliation":[{"name":"The City College of the City University of New York, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,5,31]]},"reference":[{"volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"Basu Saugata","key":"e_1_2_1_1_1","unstructured":"Saugata Basu , Richard Pollack , and Marie-Fran\u00e7oise Roy . 2003. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics , Vol. 10 . Springer-Verlag , Berlin . Saugata Basu, Richard Pollack, and Marie-Fran\u00e7oise Roy. 2003. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, Vol. 10. Springer-Verlag, Berlin."},{"volume-title":"A Panoramic View of Riemannian Geometry","key":"e_1_2_1_2_1","unstructured":"arcel Berger. 2003. A Panoramic View of Riemannian Geometry . Springer-Verlag , Berlin . arcel Berger. 2003. A Panoramic View of Riemannian Geometry. Springer-Verlag, Berlin."},{"volume-title":"Complexity and Real Computation","author":"Blum Lenore","key":"e_1_2_1_3_1","unstructured":"Lenore Blum , Felipe Cucker , Michael Shub , and Steve Smale . 1998. Complexity and Real Computation . Springer-Verlag , New York . With a foreword by Richard M. Karp. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1998. Complexity and Real Computation. Springer-Verlag, New York. With a foreword by Richard M. Karp."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_2_1_5_1","first-page":"318","article-title":"Computing over the reals: Foundations for scientific computing","volume":"53","author":"Braverman Mark","year":"2006","unstructured":"Mark Braverman and Stephen Cook . 2006 . Computing over the reals: Foundations for scientific computing . Not. Am. Math. Soc. 53 , 3 (2006), 318 -- 329 . Mark Braverman and Stephen Cook. 2006. Computing over the reals: Foundations for scientific computing. Not. Am. Math. Soc. 53, 3 (2006), 318--329.","journal-title":"Not. Am. Math. Soc."},{"volume-title":"Computability of Julia Sets. Algorithms and Computation in Mathematics","author":"Braverman Mark","key":"e_1_2_1_6_1","unstructured":"Mark Braverman and Michael Yampolsky . 2009. Computability of Julia Sets. Algorithms and Computation in Mathematics , Vol. 23 . Springer-Verlag , Berlin . Mark Braverman and Michael Yampolsky. 2009. Computability of Julia Sets. Algorithms and Computation in Mathematics, Vol. 23. Springer-Verlag, Berlin."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321944"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2015.2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300519"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90008-Y"},{"volume-title":"Metric Structures for Riemannian and Non-Riemannian Spaces (english ed.)","author":"Gromov Misha","key":"e_1_2_1_11_1","unstructured":"Misha Gromov . 2007. Metric Structures for Riemannian and Non-Riemannian Spaces (english ed.) . Birkh\u00e4user Boston, Inc. , Boston, MA . Misha Gromov. 2007. Metric Structures for Riemannian and Non-Riemannian Spaces (english ed.). Birkh\u00e4user Boston, Inc., Boston, MA."},{"key":"e_1_2_1_12_1","unstructured":"IEEE 2008. 754-2008\u2014IEEE Standard for Floating-Point Arithmetic.  IEEE 2008. 754-2008\u2014IEEE Standard for Floating-Point Arithmetic."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3121432"},{"volume-title":"Handbook of Floating-point Arithmetic","author":"Muller Jean-Michel","key":"e_1_2_1_14_1","unstructured":"Jean-Michel Muller , Nicolas Brunie , Florent de Dinechin , Claude-Pierre Jeannerod , Mioara Joldes , Vincent Lef\u00e8vre , Guillaume Melquiond , Nathalie Revol , and Serge Torres . 2018. Handbook of Floating-point Arithmetic . Birkh\u00e4user\/Springer , Cham . Second edition. Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Mioara Joldes, Vincent Lef\u00e8vre, Guillaume Melquiond, Nathalie Revol, and Serge Torres. 2018. Handbook of Floating-point Arithmetic. Birkh\u00e4user\/Springer, Cham. Second edition."},{"volume-title":"On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. ProQuest LLC","author":"Priest Douglas M.","key":"e_1_2_1_15_1","unstructured":"Douglas M. Priest . 1992. On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. ProQuest LLC , Ann Arbor, MI . Douglas M. Priest. 1992. On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. ProQuest LLC, Ann Arbor, MI."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/qjmam\/1.1.287"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321479","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3321479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:13Z","timestamp":1750204393000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3321479"],"URL":"https:\/\/doi.org\/10.1145\/3321479","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}