NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»
Доказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы пр...
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2018-04-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/345 |