Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика (сохраняя число решений) — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Т.е. если 3КНФ <tt>F</tt> полиномиально преобразуется в (граф <tt>G</tt>, число <tt>k</tt>), то количество выполняющих наборов переменных для <tt>F</tt> равно количеству клик размера <tt>k</tt> в графе <tt>G</tt>). | Т.е. если 3КНФ <tt>F</tt> полиномиально преобразуется в (граф <tt>G</tt>, число <tt>k</tt>), то количество выполняющих наборов переменных для <tt>F</tt> равно количеству клик размера <tt>k</tt> в графе <tt>G</tt>). | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 08:40, 11 марта 2021
Получите сводимость как в Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика, но дополнительно требуется, чтобы количество решений сохранялось.
Т.е. если 3КНФ F полиномиально преобразуется в (граф G, число k), то количество выполняющих наборов переменных для F равно количеству клик размера k в графе G).