Полиномиальные сводимости и 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>). | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:50, 4 мая 2023
Получите сводимость как в Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика, но дополнительно требуется, чтобы количество решений сохранялось.
Т.е. если 3КНФ F полиномиально преобразуется в (граф G, число k), то количество выполняющих наборов переменных для F равно количеству клик размера k в графе G).