Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Pull and PushPull are PSPACE-complete

2016; Elsevier BV; Volume: 628; Linguagem: Inglês

10.1016/j.tcs.2016.03.012

1879-2294

André G. Pereira, Marcus Ritt, Luciana S. Buriol,

Logic, programming, and type systems

We prove PSPACE-completeness of a broad class of moving-blocks problems similar to the well-known puzzle Sokoban. Several computational complexity results are known for moving-blocks problems. However, most of the literature is focused on problems with push moves and the complexity of many of them are still open. In this article, we study the computational complexity of moving-blocks problems with pull moves and problems with push and pull moves. Our reductions are from Nondeterministic Constraint Logic. We improve the known NP-hardness results of Pull problems to PSPACE-completeness results. We also were able to show that the whole class of PushPull problems is PSPACE-complete.