@article{oai:ipsj.ixsq.nii.ac.jp:02001550,
 author = {福永,智渉 and 大久保,誠也 and Chiho Fukunaga and Seiya Okubo},
 issue = {2},
 journal = {情報処理学会論文誌数理モデル化と応用（TOM）},
 month = {Mar},
 note = {本研究では，組合せパズルゲームの1つである，サムラインがNP完全であることを証明する．証明では，NP完全問題であるカックロからの多項式時間帰着を用いてNP完全性を示す．さらに量子アニーリングを用いた解法を提案する．具体的には，サムラインを2次式と1次式の項からなるハミルトニアンに変換する手法を提案する．また，計算機実験を行うことで，手法の妥当性を示す．, In this study, we prove that one of the combinatorial puzzle games, Sumline, is NP-complete. The proof is based on a polynomial-time reduction from KAKURO, which is an NP-complete problem, to show NP-completeness. Furthermore, we propose a method to solve the Sumline using Quantum annealing. Specifically, we propose a method to transform the Sumline into a Hamiltonian consisting of quadratic and linear terms. In addition, computer experiments are conducted to demonstrate the validity of the method.},
 pages = {1--12},
 title = {サムラインのNP完全性の証明と量子アニーリングを用いた解法について},
 volume = {18},
 year = {2025}
}