Defying Gravity: The Complexity of the Hanano Puzzle

Michael C. Chavrimootoo

Liu and Yang [LY19] recently proved the Hanano Puzzle to be ${\rm NP}$-$\leq_m^p$-hard. We prove it is in fact ${\rm PSPACE}$-$\leq_m^p$-complete. Our paper introduces the notion of a planar grid and establishes a relationship between planar grids and instances of the Nondeterministic Constraint Logic (${\rm NCL}$) problem (a known ${\rm PSPACE}$-$\leq_m^p$-complete problem [HD09]) by using graph theoretic methods, and uses this connection to guide an indirect many-one reduction from the ${\rm NCL}$ problem to the Hanano Puzzle. The technique introduced is versatile and can be reapplied to other games with gravity.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment