skip to main content


Title: Defying Gravity and Gadget Numerosity: The Complexity of the Hanano Puzzle
Using the notion of visibility representations, our paper establishes a new property of in- stances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem that is very convenient to prove the PSPACE-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show PSPACE-hardness, but we show how to bring that number from 32 down to only three in general, and down to two in a specific case! We propose it as a step towards a broader and more general framework for studying games with irreversible gravity, and use this connection to guide an indirect polynomial-time many-one reduction from the NCL problem to the Hanano Puzzle—which is NP-hard—to prove it is in fact PSPACE-complete.  more » « less
Award ID(s):
2006496
PAR ID:
10422862
Author(s) / Creator(s):
Date Published:
Journal Name:
Proceedings of the 25th International Conference on Descriptional Complexity of Formal Systems
Volume:
25
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Schmidt’s game and other similar intersection games have played an important role in recent years in applications to number theory, dynamics, and Diophantine approximation theory. These games are real games, that is, games in which the players make moves from a complete separable metric space. The determinacy of these games trivially follows from the axiom of determinacy for real games, $\mathsf {AD}_{\mathbb R}$ , which is a much stronger axiom than that asserting all integer games are determined, $\mathsf {AD}$ . One of our main results is a general theorem which under the hypothesis $\mathsf {AD}$ implies the determinacy of intersection games which have a property allowing strategies to be simplified. In particular, we show that Schmidt’s $(\alpha ,\beta ,\rho )$ game on $\mathbb R$ is determined from $\mathsf {AD}$ alone, but on $\mathbb R^n$ for $n \geq 3$ we show that $\mathsf {AD}$ does not imply the determinacy of this game. We then give an application of simple strategies and prove that the winning player in Schmidt’s $(\alpha , \beta , \rho )$ game on $\mathbb {R}$ has a winning positional strategy, without appealing to the axiom of choice. We also prove several other results specifically related to the determinacy of Schmidt’s game. These results highlight the obstacles in obtaining the determinacy of Schmidt’s game from $\mathsf {AD}$ . 
    more » « less
  2. We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. 
    more » « less
  3. Bojanczy, Mikolaj ; Chekuri, Chandra (Ed.)
    One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recently-announced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs. 
    more » « less
  4. In this paper, we investigate a certain class of tile-based pattern games through a simplified version of a recent game titled Nonads. We prove that Nonads is PSPACE-complete with a reduction from bounded 2-player constraint logic (Bounded 2CL) even when both players share the same target and there is only one type of playable tile. This has application to any grid-based pattern building game. 
    more » « less
  5. We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP[superscript]QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC[superscript]0 under uniform AC[superscript]0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures. 
    more » « less