класс NP, проверка полиномиального времени CLIQUE

Question

Проблема CLIQUE - проблема нахождения максимальной клики на графике NP-полная. То есть, Клик

а.) В НП и б.) Есть полная задача Н.П., 3-SAT для одного, , что сводится к CLIQUE в полиномиальное время.

Часть (b) выше хорошо - все в каждом ресурсе и очень хорошо объяснено. Для части (a), из того, что я знаю, нам необходимо иметь следующее: Учитывая конкретный экземпляр решения, нам нужно показать, что можно проверить в полиномиальное время, что это решение является ответом на эту проблему , Так, например, при заданном конкретном графе и подграфе, мы должны быть , чтобы проверить, является ли этот подграф кликой максимального размера в этом графе.

ресурсы, которые я читал до сих пор являются Перефразируя эту часть (а) здесь, как «легко, просто и т.д.» или «может быть показано в O (N^2) время, что данный подграф является клика/нет». Однако проверка здесь не просто, является ли это кликой, но также является ли она максимальной кликой на графике. Как это можно решить за полиномиальное время?

Что мне здесь не хватает?

Answer 1

Вы путаете оптимизации версии проблемы с решения версии проблемы.

Решение клики спрашивает, имеет ли граф клик размером k. Учитывая решение кандидата, вы можете проверить его выполнимость в полиномиальное время. Сосредоточьтесь на версиях решений для доказательств NP-полноты.

Сертификаты оптимальности для задач оптимизации действительно сложнее найти.