Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKnuth-Bendix constraint solving is NP-complete
147
0
0.0
(
0
)
Added by
Konstantin Korovin
Publication date
2002
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.
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.
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}.
Compiling quantum circuits lends itself to an elegant formulation in the language of rewriting systems on non commutative polynomial algebras $mathbb Qlangle Xrangle$. The alphabet $X$ is the set of the allowed hardware 2-qubit gates. The set of gates that we wish to implement from $X$ are elements of a free monoid $X^*$ (obtained by concatenating the letters of $X$). In this setting, compiling an idealized gate is equivalent to computing its unique normal form with respect to the rewriting system $mathcal Rsubset mathbb Qlangle Xrangle$ that encodes the hardware constraints and capabilities. This system $mathcal R$ is generated using two different mechanisms: 1) using the Knuth-Bendix completion algorithm on the algebra $mathbb Qlangle Xrangle$, and 2) using the Buchberger algorithm on the shuffle algebra $mathbb Q[L]$ where $L$ is the set of Lyndon words on $X$.
This paper discusses the hardness of finding minimal good-for-games (GFG) Buchi, Co-Buchi, and parity automata with state based acceptance. The problem appears to sit between finding small deterministic and finding small nondeterministic automata, where minimality is NP-complete and PSPACE-complete, respectively. However, recent work of Radi and Kupferman has shown that minimising Co-Buchi automata with transition based acceptance is tractable, which suggests that the complexity of minimising GFG automata might be cheaper than minimising deterministic automata. We show for the standard state based acceptance that the minimality of a GFG automaton is NP-complete for Buchi, Co-Buchi, and parity GFG automata. The proofs are a surprisingly straight forward generalisation of the proofs from deterministic Buchi automata: they use a similar reductions, and the same hard class of languages.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
