Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика (сохраняя число решений) — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Created page with "Получите сводимость как в [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КН...") |
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>). | ||
| − | [[ | + | [[Категория:Нерешенные задачи]] |
Версия 20:12, 4 октября 2020
Получите сводимость как в Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика, но дополнительно требуется, чтобы количество решений сохранялось.
Т.е. если 3КНФ F полиномиально преобразуется в (граф G, число k), то количество выполняющих наборов переменных для F равно количеству клик размера k в графе G).