Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userZig-Zag Numberlink is NP-Complete
173
0
0.0
(
0
)
Added by
Michael O'Brien
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
When can $t$ terminal pairs in an $m times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynchs 1975 proof without the ``cover all vertices constraint, and Kotsuma and Takenagas 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle emph{Numberlink}; our problem is another common form of Numberlink, sometimes called emph{Zig-Zag Numberlink} and popularized by the smartphone app emph{Flow Free}.
rate research
Read More
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer horizontally than vertically, rectangles containing | are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.
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.
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular grid graph into two induced trees (normal Yin-Yang), or into two induced connected subgraphs (Yin-Yang without $2 times 2$ rule), subject to some vertices being pre-assigned to a specific tree/subgraph.
Using the probability theory-based approach, this paper reveals the equivalence of an arbitrary NP-complete problem to a problem of checking whether a level set of a specifically constructed harmonic cost function (with all diagonal entries of its Hessian matrix equal to zero) intersects with a unit hypercube in many-dimensional Euclidean space. This connection suggests the possibility that methods of continuous mathematics can provide crucial insights into the most intriguing open questions in modern complexity theory.
The zig-zag symmetry transition is a phase transition in 1D quantum wires, in which a Wigner lattice of electrons transitions to two staggered lattices. Previous studies model this transition as a Luttinger liquid coupled to a Majorana fermion. The model exhibits interesting RG flows, involving quenching of velocities in subsectors of the theory. We suggest an extension of the model which replaces the Majorana fermion by a more general CFT; this includes an experimentally realizable case with two Majorana fermions. We analyse the RG flow both in field theory and using AdS/CFT techniques in the large central charge limit of the CFT. The model has a rich phase structure with new qualitative features, already in the two Majorana fermion case. The AdS/CFT calculation involves considering back reaction in space-time to capture subleading effects.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
