Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика (сохраняя число решений) — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 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).