Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSatisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem
104
0
0.0
(
0
)
Added by
Joerg Rothe
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Holzer and Holzer (Discrete Applied Mathematics 144(3):345--358, 2004) proved that the Tantrix(TM) rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix(TM) rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix(TM) rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP.
rate research
Read More
Holzer and Holzer (Discrete Applied Mathematics 144(3):345--358, 2004) proved that the Tantrix(TM) rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we study the three-color and two-color Tantrix(TM) rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix(TM) tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.
Transient chaos is an ubiquitous phenomenon characterizing the dynamics of phase space trajectories evolving towards a steady state attractor in physical systems as diverse as fluids, chemical reactions and condensed matter systems. Here we show that transient chaos also appears in the dynamics of certain efficient algorithms searching for solutions of constraint satisfaction problems that include scheduling, circuit design, routing, database problems or even Sudoku. In particular, we present a study of the emergence of hardness in Boolean satisfiability ($k$-SAT), a canonical class of constraint satisfaction problems, by using an analog deterministic algorithm based on a system of ordinary differential equations. Problem hardness is defined through the escape rate $kappa$, an invariant measure of transient chaos of the dynamical system corresponding to the analog algorithm, and it expresses the rate at which the trajectory approaches a solution.We show that for a given density of constraints and fixed number of Boolean variables $N$, the hardness of formulas in random $k$-SAT ensembles has a wide variation, approximable by a lognormal distribution. We also show that when increasing the density of constraints $alpha$, hardness appears through a second-order phase transition at $alpha_{chi}$ in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic. A similar behavior is found in 4-SAT as well, however, such transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter $kappa sim N^{B|alpha - alpha_{chi}|^{1-gamma}}$ with $0< gamma < 1$. We demonstrate that the transition is generated by the appearance of metastable basins in the solution space as the density of constraints $alpha$ is increased.
For Boolean satisfiability problems, the structure of the solution space is characterized by the solution graph, where the vertices are the solutions, and two solutions are connected iff they differ in exactly one variable. For this implicitly defined graph, we here study the st-connectivity and connectivity problems. Building on the work of Gopalan et al. (The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies, 2006/2009), we first investigate satisfiability problems given by CSPs, more exactly CNF(S)-formulas with constants (as considered in Schaefers famous 1978 dichotomy theorem); we prove a computational dichotomy for the st-connectivity problem, asserting that it is either solvable in polynomial time or PSPACE-complete, and an aligned structural dichotomy, asserting that the maximal diameter of connected components is either linear in the number of variables, or can be exponential; further, we show a trichotomy for the connectivity problem, asserting that it is either in P, coNP-complete, or PSPACE-complete. Next we investigate two important variants: CNF(S)-formulas without constants, and partially quantified formulas; in both cases, we prove analogous dichotomies for st-connectivity and the diameter; for for the connectivity problem, we show a trichotomy in the case of quantified formulas, while in the case of formulas without constants, we identify fragments of a possible trichotomy. Finally, we consider the connectivity issues for B-formulas, which are arbitrarily nested formulas built from some fixed set B of connectives, and for B-circuits, which are Boolean circuits where the gates are from some finite set B; we prove a common dichotomy for both connectivity problems and the diameter; for partially quantified B-formulas, we show an analogous dichotomy.
It has been known for almost three decades that many $mathrm{NP}$-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit $C$ with $n$ uninitialized inputs, $mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(frac{n}{delta})^{exp(O(t))}$ a classical assignment $yin {0,1}^n$ that maximizes the acceptance probability of $C$ up to a $delta$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < delta < 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $mathrm{NP}$-complete if $t=O(log n)$ even when $delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(log n)$, and a constant $delta<1/2$, it is $mathrm{QMA}$-complete to determine whether there exists a quantum state $mid!varphirangle in (mathbb{C}^d)^{otimes n}$ such that the acceptance probability of $Cmid!varphirangle$ is greater than $1-delta$, or whether for every such state $mid!varphirangle$, the acceptance probability of $Cmid!varphirangle$ is less than $delta$. As a consequence, under the widely believed assumption that $mathrm{QMA} eq mathrm{NP}$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
The paper explores the correspondence between balanced incomplete block designs (BIBD) and certain linear CNF formulas by identifying the points of a block design with the clauses of the Boolean formula and blocks with Boolean variables. Parallel classes in BIBDs correspond to XSAT solutions in the corresponding formula. This correspondence allows for transfers of results from one field to the other. As a new result we deduce from known satisfiability theorems that the problem of finding a parallel class in a partially balanced incomplete block design is NP-complete.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
