{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:12:30Z","timestamp":1740809550302,"version":"3.38.0"},"reference-count":15,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2025,3,1]]},"DOI":"10.1587\/transinf.2024fcp0004","type":"journal-article","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T22:12:32Z","timestamp":1723759952000},"page":"201-207","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of Yajisan-Kazusan and Stained Glass"],"prefix":"10.1587","volume":"E108.D","author":[{"given":"Chuzo","family":"IWAMOTO","sequence":"first","affiliation":[{"name":"Graduate School of Advanced Science and Engineering, Hiroshima University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryo","family":"TAKAISHI","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Engineering, Hiroshima University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] https:\/\/en.wikipedia.org\/wiki\/Yajisan-Kazusan"},{"key":"2","unstructured":"[2] https:\/\/en.wikipedia.org\/wiki\/Stained_Glass_(puzzle)"},{"key":"3","unstructured":"[3] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979."},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] S. Hand, A. Koch, P. Lafourcade, D. Miyahara, and L. Robert, \u201cCheck alternating patterns: a physical zero-knowledge proof for moon-or-sun,\u201d Proc. 18th international workshop on security (IWSEC), LNCS, vol.14128, pp.255-272, 2023. DOI:10.1007\/978-3-031-41326-1_14 10.1007\/978-3-031-41326-1_14","DOI":"10.1007\/978-3-031-41326-1_14"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] C. Iwamoto and T. Ide, \u201cFive Cells and Tilepaint are NP-complete,\u201d IEICE Trans. Inf. & Syst., vol.E105-D, no.3, pp.508-516, 2022. DOI:10.1587\/transinf.2021FCP0001 10.1587\/transinf.2021fcp0001","DOI":"10.1587\/transinf.2021FCP0001"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] C. Iwamoto and T. Ide, \u201cMoon-or-Sun, Nagareru, and Nurimeizu are NP-complete,\u201d IEICE Trans. Fundamentals, vol.E105-A, no.9, pp.1187-1194, 2022. DOI:10.1587\/transfun.2021DMP0006 10.1587\/transfun.2021dmp0006","DOI":"10.1587\/transfun.2021DMP0006"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] C. Iwamoto and S. Oda, \u201cComputational complexity of Sukoro,\u201d IEICE Trans. Inf. & Syst. (Japanese Edition), vol.J106-D, no.5, pp.357-361, 2023. DOI:10.14923\/transinfj.2022JDL8010 10.14923\/transinfj.2022jdl8010","DOI":"10.14923\/transinfj.2022JDL8010"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] C. Iwamoto and T. Tokunaga, \u201cChoco Banana is NP-complete,\u201d IEICE Trans. Fundamentals, vol.E107-A, no.9, pp.1488-1491, 2024. 10.1587\/transfun.2023dml0001","DOI":"10.1587\/transfun.2023DML0001"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] W. Mulzer and G. Rote, \u201cMinimum-weight triangulation is NP-hard,\u201d J. ACM, vol.55, no.2, pp.1-29, 2008. DOI:10.1145\/1346330.1346336 10.1145\/1346330.1346336","DOI":"10.1145\/1346330.1346336"},{"key":"10","unstructured":"[10] Nikoli: Japanese Number Puzzles, NIKOLI Co., Ltd., Tokyo, Japan, ISBN13: 9784890728503, 2019."},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki, \u201cPhysical ZKP protocols for Nurimisaki and Kurodoko,\u201d Theor. Comput. Sci., vol.972, 114071, 2023. DOI:10.1016\/j.tcs.2023.114071 10.1016\/j.tcs.2023.114071","DOI":"10.1016\/j.tcs.2023.114071"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] S. Ruangwises, \u201cAn improved physical ZKP for nonogram and nonogram color,\u201d J. Comb. Optim., vol.45, no.5, 2023. DOI:10.1007\/s10878-023-01050-5 10.1007\/s10878-023-01050-5","DOI":"10.1007\/s10878-023-01050-5"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] S. Ruangwises, \u201cPhysical zero-knowledge proofs for five cells,\u201d Proc. 8th international conference on cryptology and information security in Latin America (LATINCRYPT), Lecture Notes in Computer Science, vol.14168, pp.315-330, 2023. DOI:10.1007\/978-3-031-44469-2_16 10.1007\/978-3-031-44469-2_16","DOI":"10.1007\/978-3-031-44469-2_16"},{"key":"14","unstructured":"[14] S. Ruangwises, \u201cToichika is NP-complete,\u201d Proc. 25th Indonesia-Japan conference on discrete and computational geometry, graphs, and games (IJCDCG3), p.96, 2023."},{"key":"15","unstructured":"[15] S. Ruangwises, \u201cNondango is NP-complete,\u201d Proc. 40th European Workshop on Computational Geometry, pp.1:1-1:10, Ioannina, Greece, 2024."}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0004\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T03:33:17Z","timestamp":1740799997000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0004\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,1]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2024fcp0004","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2025,3,1]]},"article-number":"2024FCP0004"}}