informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-345Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGNP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»БаркетовМ. С.Объединенный институт проблем информатики НАН БеларусиBelarus20111004201803(31)512Copyright © Баркетов М.С., 20182018Баркетов М.С.Баркетов М.С.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/345

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

ReferencesGarey, M.R. Computers and intractability: A guide to the theory of NP-completeness /Garey, M.R. Computers and intractability: A guide to the theory of NP-completeness /M.R. Garey, D.S. Johnson. – San Francisco : Freeman, 1979. – 340 p.M.R. Garey, D.S. Johnson. – San Francisco : Freeman, 1979. – 340 p.Riesel, H. Prime numbers and computer methods for factorization / H. Riesel. – Boston, 1994.Riesel, H. Prime numbers and computer methods for factorization / H. Riesel. – Boston, 1994.Кононов, А.В. Комбинаторная сложность составления расписаний для работ с простымКононов, А.В. Комбинаторная сложность составления расписаний для работ с простымлинейным ростом длительностей / А.В. Кононов // Дискретный анализ и исследование операций. – 1996. – Т. 3, № 2. – С. 15–32.линейным ростом длительностей / А.В. Кононов // Дискретный анализ и исследование операций. – 1996. – Т. 3, № 2. – С. 15–32.Баркетов, М.С. О вычислительной сложности задачи Product Partition / М.С. Баркетов,Баркетов, М.С. О вычислительной сложности задачи Product Partition / М.С. Баркетов,М.Я. Ковалев // Доклады НАН Беларуси. – 2007. – Т. 51, № 3. – С. 29–31.М.Я. Ковалев // Доклады НАН Беларуси. – 2007. – Т. 51, № 3. – С. 29–31.

The authors declare that there are no conflicts of interest present.