اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدZig-Zag Numberlink is NP-Complete
171
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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}.
قيم البحث
اقرأ أيضاً
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 exac
tly 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 h
ole. 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 induce
d 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 He
ssian 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 m
odel 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
