✦ LIBER ✦

The STO problem is NP-complete

✍ Scribed by P. Krysta; L. Pacholski

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 233 KB
Volume: 27
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1998.0249

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that the problem STO of deciding whether or not a finite set E of term equations is subject to occur-check is in NP. E is subject to occur-check if the execution of the Martelli-Montanari unification algorithm gives for input E a set E ∪ {x = t}, where t = x and x appears in t. Apt et al. (1994) proved that STO is NP-hard leaving the problem of NP-completeness open.

📜 SIMILAR VOLUMES

The STO-problem is NP-hard

✍ Krzysztof R. Apt; Peter van Emde Boas; Angelo Welling 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

A finite set of term equations \(E\) is called subject to the occur-check (STO) if a sequence of actions of the Martelli-Montanari unification algorithm starts with \(E\) and ends with a failure due to occur-check. We prove here that the problem of deciding whether \(E\) is STO is NP-hard.

Testing Orientability for Matroids is NP

Testing Orientability for Matroids is NP-Complete

✍ Jürgen Richter-Gebert 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 146 KB

Matroids and oriented matroids are fundamental objects in combinatorial geometry. While matroids model the behavior of vector configurations over general fields, oriented matroids model the behavior of vector configurations over ordered fields. For every oriented matroid there is a corresponding und

DNA Models and Algorithms for NP-Complet

DNA Models and Algorithms for NP-Complete Problems

✍ Eric Bach; Anne Condon; Elton Glaser; Celena Tanguay 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A goal of research on DNA computing is to solve problems that are beyond the capabilities of the fastest silicon-based supercomputers. Adleman and Lipton present exhaustive search algorithms for 3Sat and 3-coloring, which can only be run on small instances and, hence, are not practical. In this pape

NP completeness of the edge precoloring

NP completeness of the edge precoloring extension problem on bipartite graphs

✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

The Real Dimension Problem Is NPR-Comple

The Real Dimension Problem Is NPR-Complete

✍ Pascal Koiran 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 123 KB

Recognizing triangle-free graphs with in

Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete

✍ Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 250 KB 👁 2 views

An induced path-cycle double cover (IPCDC) of a simple graph G is a family F Å {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ʝ F j x M, then F i ʝ F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in pr