{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T12:59:12Z","timestamp":1774875552130,"version":"3.50.1"},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Open Syst. Inf. Dyn."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> For SAT problem, which is known to be NP-complete, Ohya and Masuda found a quantum algorithm calculating a given boolean function for all truth assignments. They showed that we can decide whether this boolean function is satisfiable or not in polynomial time if a certain superposed state can be detected physically, which turns out to be related to an amplification process. Then Ohya and Volovich realized this amplification by means of chaos dynamics [4, 5]. In this paper, we study the complexity of the SAT algorithm by rigorously counting the steps of OMV algorithm discussed previously in [1, 2, 4, 5]. <\/jats:p>","DOI":"10.1142\/s1230161208000158","type":"journal-article","created":{"date-parts":[[2008,6,13]],"date-time":"2008-06-13T10:55:40Z","timestamp":1213354540000},"page":"173-187","source":"Crossref","is-referenced-by-count":8,"title":["Rigorous Estimation of Computational Complexity for OMV SAT Algorithm"],"prefix":"10.1142","volume":"15","author":[{"given":"Satoshi","family":"Iriyama","sequence":"first","affiliation":[{"name":"Tokyo University of Science, Depertment of Information Science, 8641, Yamasaki, Noda City, Chiba, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masanori","family":"Ohya","sequence":"additional","affiliation":[{"name":"Tokyo University of Science, Depertment of Information Science, 8641, Yamasaki, Noda City, Chiba, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009651417615"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1088\/1464-4266\/5\/6\/015"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0034-4877(03)90002-4"},{"key":"rf6","unstructured":"J.\u00a0Franco, Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society, 1997)\u00a0pp. 19\u2013152."},{"key":"rf7","volume-title":"Computers and Intractability: A guide to the theory of NP-Completeness","author":"Johnson G.","year":"1979"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/9789812774491_0017"}],"container-title":["Open Systems &amp; Information Dynamics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1230161208000158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:56:21Z","timestamp":1565142981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1230161208000158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":6,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S1230161208000158"],"URL":"https:\/\/doi.org\/10.1142\/s1230161208000158","relation":{},"ISSN":["1230-1612","1793-7191"],"issn-type":[{"value":"1230-1612","type":"print"},{"value":"1793-7191","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}