1. Объединенный институт проблем информатики Минск, Сурганова, 6

УДК: 519.8

Реферат:

Доказывается NP-полнота в сильном смысле задачи 3 РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ. В этой задаче дано множество из 3m элементов A={a₁, a₂, …, a_3m} и для каждого элемента a_i дан его размер s(a_i)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A₁, A₂,…, A_m так, чтобы произведения размеров элементов каждого из подмножеств A_i, 1 ≤ i ≤ m, были равны между собой.