اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGeometric Embeddability of Complexes is $exists mathbb R$-complete
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $mathbb R^d$ is complete for the Existential Theory of the Reals for all $dgeq 3$ and $kin{d-1,d}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real root. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.
قيم البحث
اقرأ أيضاً
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.
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed.
The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is $existsmathbb R$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are $existsmathbb R$-complete: $bullet$ simple polygons, each of which has at most 8 corners, into a square, $bullet$ convex objects bounded by line segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are $existsmathbb R$-complete: $bullet$ objects bounded by segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by segments and hyperbolic curves.
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 properties of the homology of different geometric filtered complexes (such as Vietoris-Rips, Cech and witness complexes) built on top of precompact spaces. Using recent developments in the theory of topological persistence
we provide simple and natural proofs of the stability of the persistent homology of such complexes with respect to the Gromov--Hausdorff distance. We also exhibit a few noteworthy properties of the homology of the Rips and Cech complexes built on top of compact spaces.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
