𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computing the norm ∥ A ∥∞,1 is NP-hard ∗

✍ Scribed by Rohn, Jiří

Book ID
120055173
Publisher
Taylor and Francis Group
Year
2000
Tongue
English
Weight
221 KB
Volume
47
Category
Article
ISSN
0308-1087

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Minimum-weight triangulation is NP-hard
Minimum-weight triangulation is NP-hard
✍ Mulzer, Wolfgang; Rote, Günter 📂 Article 📅 2008 🏛 Association for Computing Machinery 🌐 English ⚖ 707 KB
Minimum-weight triangulation is NP-hard
Minimum-weight triangulation is NP-hard
✍ Mulzer, Wolfgang; Rote, Günter 📂 Article 📅 2008 🏛 Association for Computing Machinery 🌐 English ⚖ 707 KB
The STO-problem is NP-hard
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.