Preview

Информатика

Расширенный поиск

NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»

Аннотация

Доказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.
В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы произведения размеров элементов каждого из подмножеств Ai, 1 ≤ i ≤ m, были равны между собой.

Об авторе

М. С. Баркетов
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

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.


Рецензия

Для цитирования:


Баркетов М.С. NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ». Информатика. 2011;(3(31)):5-12.

Просмотров: 466


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)