Класс NP, проверка за полиномиальное время КЛИК
Задача CLIQUE - задача определения максимальной клики в графе является NP-полной. То есть КЛИК является
a.) в NP и b.) существует проблема полного NP, 3-SAT для одного, которая сводится к CLIQUE за полиномиальное время.
Часть (b) выше в порядке - все в каждом ресурсе и очень хорошо объяснены. Что касается части (а), из того, что я знаю, нам нужно следующее: учитывая конкретный экземпляр решения, мы должны показать, что за полиномиальное время можно проверить, что это решение является ответом на эту проблему. Так, например, учитывая конкретный граф и его подграф, мы должны быть в состоянии проверить, является ли этот подграф кликой максимального размера в этом графе.
Ресурсы, которые я до сих пор читал, формулируют эту часть (а) здесь как "легкую, прямую и т. Д." Или "за O(n^2) может быть показано, что данный подграф является кликой / нет". Однако проверка здесь заключается не только в том, является ли это кликой, но также является ли она максимальной кликой на графике. Как это можно решить за полиномиальное время?
Что мне здесь не хватает?
1 ответ
Вы путаете оптимизационную версию проблемы с версией решения проблемы.
Версия клики для принятия решения спрашивает, имеет ли граф клику размера k. Учитывая возможное решение, вы можете проверить его выполнимость за полиномиальное время. Сосредоточьтесь на версиях решения для NP-полноты доказательства.
Сертификаты оптимальности для задач оптимизации действительно сложнее найти.