NP-completeness of Arithmetical Restorations

• Tomomi, Matsui

抄録

This paper deals with a variation of crypt-arithmetics, called “arithmetical restorations.” Arithmetical restorations are problems dealing with the reconstruction of arithmetical sums from which various digits have been erased. We show the NP-completeness of a problem deciding whether a given instance of arithmetical restorations of multiplication sums has a solution or not.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online)DOI http://dx.doi.org/10.2197/ipsjjip.21.402------------------------------

This paper deals with a variation of crypt-arithmetics, called “arithmetical restorations.” Arithmetical restorations are problems dealing with the reconstruction of arithmetical sums from which various digits have been erased. We show the NP-completeness of a problem deciding whether a given instance of arithmetical restorations of multiplication sums has a solution or not.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online)DOI http://dx.doi.org/10.2197/ipsjjip.21.402------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 54 (5), 2013-05-15

キーワード

• [特集：パズルの数理] crypt-arithmetic, word crypt-arithmetics, alphametics, NP-complete

詳細情報

• CRID: 1050282812879907968
• NII論文ID: 110009579785
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00092111/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles