Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDots & Boxes is PSPACE-complete
308
0
0.0
(
0
)
Added by
Kevin Buchin
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Childs Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.
rate research
Read More
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other semantic equivalences, strong and weak simulation preorder are decidable for OCN, but the computational complexity was an open problem. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.
Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no hole. When all odd numbers are placed it is in P, whereas it is still NP-hard when all numbers of the form $3k+1$ are placed.
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 the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon $mathcal P$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $mathcal P$. It is known that MCC is $mathsf{NP}$-hard [Culberson & Reckhow: Covering polygons is hard, FOCS 1988/Journal of Algorithms 1994] and in $existsmathbb{R}$ [ORourke: The complexity of computing minimum convex covers for polygons, Allerton 1982]. We prove that MCC is $existsmathbb{R}$-hard, and the problem is thus $existsmathbb{R}$-complete. In other words, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution. If a cover for our constructed polygon exists, then so does a cover consisting entirely of triangles. As a byproduct, we therefore also establish that it is $existsmathbb{R}$-complete to decide whether $k$ triangles cover a given polygon. The issue that it was not known if finding a minimum cover is in $mathsf{NP}$ has repeatedly been raised in the literature, and it was mentioned as a long-standing open question already in 2001 [Eidenbenz & Widmayer: An approximation algorithm for minimum convex cover with logarithmic performance guarantee, ESA 2001/SIAM Journal on Computing 2003]. We prove that assuming the widespread belief that $mathsf{NP} eqexistsmathbb{R}$, the problem is not in $mathsf{NP}$. An implication of the result is that many natural approaches to finding small covers are bound to give suboptimal solutions in some cases, since irrational coordinates of arbitrarily high algebraic degree can be needed for the corners of the pieces in an optimal solution.
Neuromorphic computing is a non-von Neumann computing paradigm that performs computation by emulating the human brain. Neuromorphic systems are extremely energy-efficient and known to consume thousands of times less power than CPUs and GPUs. They have the potential to drive critical use cases such as autonomous vehicles, edge computing and internet of things in the future. For this reason, they are sought to be an indispensable part of the future computing landscape. Neuromorphic systems are mainly used for spike-based machine learning applications, although there are some non-machine learning applications in graph theory, differential equations, and spike-based simulations. These applications suggest that neuromorphic computing might be capable of general-purpose computing. However, general-purpose computability of neuromorphic computing has not been established yet. In this work, we prove that neuromorphic computing is Turing-complete and therefore capable of general-purpose computing. Specifically, we present a model of neuromorphic computing, with just two neuron parameters (threshold and leak), and two synaptic parameters (weight and delay). We devise neuromorphic circuits for computing all the {mu}-recursive functions (i.e., constant, successor and projection functions) and all the {mu}-recursive operators (i.e., composition, primitive recursion and minimization operators). Given that the {mu}-recursive functions and operators are precisely the ones that can be computed using a Turing machine, this work establishes the Turing-completeness of neuromorphic computing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
