Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWalking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
80
0
0.0
(
0
)
Added by
Jayson Lynch
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the open and close tunnel sets the gadgets state to open and closed, respectively, while the traverse tunnel can be traversed if and only if the door is in the open state. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of such door gadgets, removing the traditional need for crossover gadgets and thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Our result holds in all but one of the possible local planar embedding of the open, close, and traverse tunnels within a door gadget; in the one remaining case, we prove NP-hardness. We also introduce and analyze a simpler type of door gadget, called the self-closing door. This gadget has two states and only two tunnels, similar to the open and traverse tunnels of doors, except that traversing the traverse tunnel also closes the door. In a variant called the symmetric self-closing door, the open tunnel can be traversed if and only if the door is closed. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of either type of self-closing door. Then we apply this framework to prove new PSPACE-hardness results for eight different 3D Mario games and Sokobond.
rate research
Read More
The finite models of a universal sentence $Phi$ in a finite relational signature are the age of a homogeneous structure if and only if $Phi$ has the amalgamation property. We prove that the computational problem whether a given universal sentence $Phi$ has the amalgamation property is PSPACE-hard, even if $Phi$ is additionally Horn and the signature of $Phi$ only contains relation symbols of arity at most three. The decidability of the problem remains open.
We prove PSPACE-completeness of two classic types of Chess problems when generalized to n-by-n boards. A retrograde problem asks whether it is possible for a position to be reached from a natural starting position, i.e., whether the position is valid or legal or reachable. Most real-world retrograde Chess problems ask for the last few moves of such a sequence; we analyze the decision question which gets at the existence of an exponentially long move sequence. A helpmate problem asks whether it is possible for a player to become checkmated by any sequence of moves from a given position. A helpmate problem is essentially a cooperative form of Chess, where both players work together to cause a particular player to win; it also arises in regular Chess games, where a player who runs out of time (flags) loses only if they could ever possibly be checkmated from the current position (i.e., the helpmate problem has a solution). Our PSPACE-hardness reductions are from a variant of a puzzle game called Subway Shuffle.
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago [BDH+04]. Our reduction is from 3-Partition, similar to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger $k$-omino pieces is NP-complete even when the board starts empty, even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font.
Consider $n^2-1$ unit-square blocks in an $n times n$ square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variation of Rush Hour with only $1 times 1$ cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical $1 times 2$ and horizontal $2 times 1$ movable blocks and 4-color Subway Shuffle.
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even $Delta$-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even $Delta$-matroids, we then extend the tractability result to larger classes of $Delta$-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely co-independent, compact, local, linear and binary, with the following caveat: we represent $Delta$-matroids by lists of tuples, while the last two use a representation by matrices. Since an $ntimes n$ matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary $Delta$-matroids.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
