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.
翻译：刘阳(LY19)最近证明花野的拼图是$$rm NP}$-$leq_m ⁇ p$-hard。我们证明它实际上是$@rm PSPACE}$-$\leq_m ⁇ p$-comful。我们的论文引入了平面网格的概念,并在平面网格和不确定性约束逻辑($rm NCL}$)实例之间建立了关系。 通过使用图表理论方法,我们证明它实际上是$@rm PSPACE}$-$leq_m ⁇ p$-comple proble proble 问题[HD09]。我们的文件用这个连接来引导从$rm NCL$问题到 Hanano 拼图的间接多一减。 引入的技术是多功能化的, 并且可以重重地重新应用到其他游戏。
相关内容
微信扫码咨询专知VIP会员