1-PushingMachine is <b>PSPACE</b>-complete

Based on two puzzle games for mobile phones, Yang introduced the k-PushingMachine problem and showed that the 2-PushingMachine problem is PSPACE-complete. In this paper, we improve Yang's result by showing that the 1-PushingMachine is also PSPACE-complete, even without walls, by applying the door gadget framework.

Authors

Zhujun Zhang (ORCID: https://orcid.org/0000-0001-8301-785X)
Chao Yang (ORCID: https://orcid.org/0000-0003-4225-9566)

Institutions

Guangdong University of Foreign Studies (CN)
Beijing Institute of Big Data Research (CN)

Publication Details

Journal: Journal of Information Processing
Published: 2025-01-01
DOI: https://doi.org/10.2197/ipsjjip.33.1071
Primary Topic: Artificial Intelligence in Games
Type: article
Field-Weighted Citation Impact: 0.00

Funders

National Natural Science Foundation of China
Guangdong University of Foreign Studies

Controls

|||

ALL TIME

JAN

FEB

MAR

APR

MAY

JUN

JUL

AUG

SEP

OCT

article

1-PushingMachine is PSPACE-complete

Zhujun Zhang, Chao Yang

Jan 1, 2025

Journal of Information Processing

Artificial Intelligence in Games

article

1-PushingMachine is PSPACE-complete

Zhujun Zhang, Chao Yang

January 1, 2025article en

Abstract

Based on two puzzle games for mobile phones, Yang introduced the k-PushingMachine problem and showed that the 2-PushingMachine problem is PSPACE-complete. In this paper, we improve Yang's result by showing that the 1-PushingMachine is also PSPACE-complete, even without walls, by applying the door gadget framework.

Journal of Information ProcessingVol. 33(0)

Guangdong University of Foreign Studies (CN), Beijing Institute of Big Data Research (CN)

National Natural Science Foundation of China, Guangdong University of Foreign Studies

Openalex Percentile: Top 79%

Artificial Intelligence in Games

DOI Open Access PDF OpenAlex

AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

1-PushingMachine is <b>PSPACE</b>-complete — Zhujun Zhang, Chao Yang · Journal of Information Processing (2025) | TGRS Research Map | TGRS