虫食い算と覆面算の計算複雑性について

• Item type: SIG Technical Reports(1)
• 公開日: 2024-08-29
• タイトル: 虫食い算と覆面算の計算複雑性について
• タイトル / 言語: en
• タイトル: On the Computational Complexity of Arithmetical Restorations and Cryptarithms
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者名: 入野, 耀太; 鎌田, 斗南; 上原, 隆平
• 著者名(英): Yota, Irino; Tonan, Kamata; Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，ペンシルパズルの一種である覆面算と虫食い算の計算複雑性について考察する．覆面算とは与えられた各桁が記号で構成される筆算の計算式に対して，異なる記号に異なる数字を割り当てることで計算式を成立させるパズルである．また，虫食い算とは所々が空欄に置き換えられた筆算を成立させるように，空欄に数字を割り当てるパズルである．覆面算と虫食い算はそれぞれ，いくつかの設定下で計算量の解析が行われている．具体的には，2 数の加算の覆面算については Eppstein，2 数の乗算の虫食い算については Matsui によって NP 完全性が示されている．上記の先行研究に対して，本研究では覆面算と虫食い算の計算複雑性について以下の結果を得た．まず，覆面算について，2数の乗算と減算の場合について NP 完全問題であることを，2 数の加算の場合からの帰着によって証明した．また，2 数の除算の場合についても同様に NP 完全問題であることを2数の減算からの帰着によって証明した．次に，虫食い算について，2 数の加算と減算の場合に，動的計画法による線形時間アルゴリズムが存在することを示した．また，2 数の除算の場合に NP 完全問題であることを，乗算の場合から帰着することで証明した．これにより，虫食い算と覆面算の双方に対して，全ての四則演算での計算複雑性が明らかになった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we show the computational complexity of two types of pencil puzzles, known as cryptarithms and arithmetical restorations. Cryptarithm is a puzzle in which each digit of a given longhand arithmetic expression is replaced by letters. The objective is to assign a unique digit to each letter, such that the expression holds true. On the other hand, arithmetical restorations involve a longhand arithmetic expression where certain digits are replaced with blanks. The task is to appropriately assign digits to these blanks to make the arithmetic operation valid. The cryptarithms and arithmetical restorations have each been analyzed for computational complexity under several conditions. Eppstein has shown NP-completeness for cryptarithms of addition of two numbers, while Matsui has proven it for arithmetical restorations of multiplication of two numbers. First, we proved that cryptarithms are NP-complete for the case of multiplication and subtraction of two numbers by reduction from the case of addition of two numbers. We also proved NP-completeness for the case of division of two numbers by reduction from the case of subtraction of two numbers. Next, for arithmetical restorations of addition and subtraction of two numbers, we develop a linear-time algorithm based on dynamic programming. We also proved that it is NP-complete on the case of division of two numbers by the reduction from the multiplication. As a result, we showed the computational complexity in all four arithmetical operations for both arithmetical restorations and cryptarithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-199, 号 6, p. 1-8, 発行日 2024-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会