๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The STO-problem is NP-hard

โœ Scribed by Krzysztof R. Apt; Peter van Emde Boas; Angelo Welling

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
209 KB
Volume
18
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

The STO problem is NP-complete
The STO problem is NP-complete
โœ P. Krysta; L. Pacholski ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 233 KB

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. (

Alignment and Distribution Is Not (Alway
Alignment and Distribution Is Not (Always) NP-Hard
โœ Vincent Boudet; Fabrice Rastello; Yves Robert ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 293 KB

In this paper, an efficient algorithm to simultaneously implement array alignment and dataร‚computation distribution is introduced and evaluated. We revisit previous work of J. Li and M. Chen (in ``Frontiers 90: The Third Symposium on the Frontiers of Massively Parallel Computation, '' pp. 424 433, C

Finding MAPs for belief networks is NP-h
Finding MAPs for belief networks is NP-hard
โœ Solomon Eyal Shimony ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 638 KB

Given a probabilistic world model, an important problem is to find the maximum a-posteriori probability (MAP) instantiation of all the random variables given the evidence. Numerous researchers using such models employ some graph representation for the distributions, such as a Bayesian belief network

Two NP-Hard Art-Gallery Problems for Ort
Two NP-Hard Art-Gallery Problems for Ortho-Polygons
โœ Dietmar Schuchardt; Hans-Dietrich Hecker ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 292 KB

## Abstract D. T. Lee and A. K. Lin [2] proved that VERTEXโ€GUARDING and POINTโ€GUARDING are NPโ€hard for simple polygons. We prove that those problems are NPโ€hard for orthoโ€polygons, too.