2026-07-21T20:02:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25731 2026-06-23T12:45:23Z ddc:004 open_access

A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles Chapman, Brynmor Chung, Lily Demaine, Erik D. Irino, Yota Hendrickson, Della Kamata, Tonan Uehara, Ryuhei arithmetical restoration cryptarithms polynomial hierarchy uniqueness quantifier puzzle complexity In arithmetic puzzles, a partially specified arithmetic expression must be completed to make the computation valid. Arithmetical restoration puzzles require filling in missing digits, while cryptarithms involve assigning digits to letters. The Japanese term mushikui-zan ("bookwormed arithmetic") commonly refers to arithmetical restorations, where we imagine the missing digits have been eaten by a bookworm. Puzzle creator Yousuke Ikeda proposed a new type of puzzle in which a previously designed bookwormed arithmetic with multiplication - known to have a unique solution - has itself been "bookwormed", that is, partially erased. The goal is to restore the specified blanks so that the resulting bookwormed puzzle again has a unique solution. We further generalize this framework: for each k ≥ 2, we define level-k puzzles as those in which type-k blanks must be filled to make the resulting level-(k{-}1) puzzle uniquely solvable. We study the level-k versions of the Boolean satisfiability problem, and show that they form a hierarchy of Σ^P_k-complete decision problems, tightly matching the levels of the polynomial hierarchy. As applications, we show that the level-k arithmetical restoration problem with multiplication is Σ^P_k-complete, as is the level-k cryptarithm problem. On the positive side, we show that level-2 arithmetical restoration puzzles with addition are solvable in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Brynmor Chapman and Lily Chung and Erik D. Demaine and Yota Irino and Della Hendrickson and Tonan Kamata and Ryuhei Uehara 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.12 urn:nbn:de:0030-drops-257311 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode