NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»
Abstract
Доказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.
В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы произведения размеров элементов каждого из подмножеств Ai, 1 ≤ i ≤ m, были равны между собой.
References
1. Garey, M.R. Computers and intractability: A guide to the theory of NP-completeness /
2. M.R. Garey, D.S. Johnson. – San Francisco : Freeman, 1979. – 340 p.
3. Riesel, H. Prime numbers and computer methods for factorization / H. Riesel. – Boston, 1994.
4. Кононов, А.В. Комбинаторная сложность составления расписаний для работ с простым
5. линейным ростом длительностей / А.В. Кононов // Дискретный анализ и исследование операций. – 1996. – Т. 3, № 2. – С. 15–32.
6. Баркетов, М.С. О вычислительной сложности задачи Product Partition / М.С. Баркетов,
7. М.Я. Ковалев // Доклады НАН Беларуси. – 2007. – Т. 51, № 3. – С. 29–31.
Review
For citations:
. Informatics. 2011;(3(31)):5-12. (In Russ.)
Views: 499
Email this article 