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

The planar -means problem is NP-hard

โœ Scribed by Meena Mahajan; Prajakta Nimbhorkar; Kasturi Varadarajan


Book ID
113927358
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
282 KB
Volume
442
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.


๐Ÿ“œ 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.