✦ LIBER ✦

The minimum-length generator sequence problem is NP-hard

✍ Scribed by S Even; O Goldreich

Publisher: Elsevier Science
Year: 1981
Tongue: English
Weight: 148 KB
Volume: 2
Category: Article
ISSN: 0196-6774
DOI: 10.1016/0196-6774(81)90029-8

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.

On the complexity of test case generatio

On the complexity of test case generation for NP-hard problems

✍ Laura A. Sanchis 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 562 KB

Problem of optimizing the number of bloc

Problem of optimizing the number of block accesses in performing relational join is NP-hard

✍ Farshad Fotouhi; Sakti Pramanik 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 665 KB

Perfect matching for regular graphs is A

Perfect matching for regular graphs is AC0-hard for the general matching problem

✍ Elias Dahlhaus; Marek Karpinski 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 491 KB