Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPSPACE-completeness of Pulling Blocks to Reach a Goal
163
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
We prove PSPACE-completeness of all but one problem in a large space of pulling-block problems where the goal is for the agent to reach a target destination. The problems are parameterized by whether pulling is optional, the number of blocks which can be pulled simultaneously, whether there are fixed blocks or thin walls, and whether there is gravity. We show NP-hardness for the remaining problem, Pull?-1FG (optional pulling, strength 1, fixed blocks, with gravity).
rate research
Read More
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.
In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from exact to approximate solution for a host of such problems. As one (notable) example, we show that the Closest-LCS-Pair problem (Given two sets of strings $A$ and $B$, compute exactly the maximum $textsf{LCS}(a, b)$ with $(a, b) in A times B$) is equivalent to its approximation version (under near-linear time reductions, and with a constant approximation factor). More generally, we identify a class of problems, which we call BP-Pair-Class, comprising both exact and approximate solutions, and show that they are all equivalent under near-linear time reductions. Exploring this class and its properties, we also show: $bullet$ Under the NC-SETH assumption (a significantly more relaxed assumption than SETH), solving any of the problems in this class requires essentially quadratic time. $bullet$ Modest improvements on the running time of known algorithms (shaving log factors) would imply that NEXP is not in non-uniform $textsf{NC}^1$. $bullet$ Finally, we leverage our techniques to show new barriers for deterministic approximation algorithms for LCS. At the heart of these new results is a deep connection between interactive proof systems for bounded-space computations and the fine-grained complexity of exact and approximate solutions to problems in P. In particular, our results build on the proof techniques from the classical IP = PSPACE result.
We prove that Strings-and-Coins -- the combinatorial two-player game generalizing the dual of Dots-and-Boxes -- is strongly PSPACE-complete on multigraphs. This result improves the best previous result, NP-hardness, argued in Winning Ways. Our result also applies to the Nimstring variant, where the winner is determined by normal play; indeed, one step in our reduction is the standard reduction (also from Winning Ways) from Nimstring to Strings-and-Coins.
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.
In this paper we consider the problems of testing isomorphism of tensors, $p$-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, and cryptography. These problems can all be cast as orbit problems on multi-way arrays under different group actions. Our first two main results are: 1. All the aforementioned isomorphism problems are equivalent under polynomial-time reductions, in conjunction with the recent results of Futorny-Grochow-Sergeichuk (Lin. Alg. Appl., 2019). 2. Isomorphism of $d$-tensors reduces to isomorphism of 3-tensors, for any $d geq 3$. Our results suggest that these isomorphism problems form a rich and robust equivalence class, which we call Tensor Isomorphism-complete, or TI-complete. We then leverage the techniques used in the above results to prove two first-of-their-kind results for Group Isomorphism (GpI): 3. We give a reduction from GpI for $p$-groups of exponent $p$ and small class ($c < p$) to GpI for $p$-groups of exponent $p$ and class 2. The latter are widely believed to be the hardest cases of GpI, but as far as we know, this is the first reduction from any more general class of groups to this class. 4. We give a search-to-decision reduction for isomorphism of $p$-groups of exponent $p$ and class 2 in time $|G|^{O(log log |G|)}$. While search-to-decision reductions for Graph Isomorphism (GI) have been known for more than 40 years, as far as we know this is the first non-trivial search-to-decision reduction in the context of GpI. Our main technique for (1), (3), and (4) is a linear-algebraic analogue of the classical graph coloring gadget, which was used to obtain the search-to-decision reduction for GI. This gadget construction may be of independent interest and utility. The technique for (2) gives a method for encoding an arbitrary tensor into an algebra.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
