NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»
Доказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы пр...
Saved in:
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2018-04-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543209633349632 |
|---|---|
| collection | DOAJ |
| description | Доказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы произведения размеров элементов каждого из подмножеств Ai, 1 ≤ i ≤ m, были равны между собой. |
| format | Article |
| id | doaj-art-38d1ada422774bf68e0461096c357519 |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2018-04-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-38d1ada422774bf68e0461096c3575192025-02-03T11:51:44ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012018-04-0103(31)512326NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ»0Объединенный институт проблем информатики НАН БеларусиДоказывается NP-полнота в сильном смысле задачи 3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ.В этой задаче дано множество из 3m элементов A={a1, a2, …, a3m} и для каждого элемента ai дан его размер s(ai)∈Z+. Необходимо определить, можно ли разбить это множество на m трехэлементных подмножеств A1, A2,…, Am так, чтобы произведения размеров элементов каждого из подмножеств Ai, 1 ≤ i ≤ m, были равны между собой.https://inf.grid.by/jour/article/view/345 |
| spellingShingle | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» Informatika |
| title | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» |
| title_full | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» |
| title_fullStr | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» |
| title_full_unstemmed | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» |
| title_short | NP-ПОЛНОТА В СИЛЬНОМ СМЫСЛЕ ЗАДАЧИ «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» |
| title_sort | np полнота в сильном смысле задачи 3 разбиение произведения |
| url | https://inf.grid.by/jour/article/view/345 |