2026-03-10T22:23:52Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00231463 2025-01-19T10:45:14Z 1164:2735:11166:11409

サムラインのNP完全性の証明と量子アニーリングを用いた解法について 福永, 智渉 大久保, 誠也 本研究では，組合せパズルゲームの 1 つであるサムラインが，NP 完全であることを証明する．また，量子アニーリングを用いた解法を提案する．具体的にはまず，サムラインの NP 完全性について，カックロからの多項式時間帰着を示すことによって証明する．次に，サムラインをイジングモデルの基底状態探索問題として表現することにより，量子アニーリングによる解法を提案する．最後に，計算機実験により，提案手法の妥当性を示す． 情報処理学会 2023-12-04 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/231463 2188-8833 AN10505667 研究報告数理モデル化と問題解決（MPS） 2023-MPS-146 9 1 6 https://ipsj.ixsq.nii.ac.jp/record/231463/files/IPSJ-MPS23146009.pdf application/pdf 1.1 MB 2025-12-04