Проблема CLIQUE — задача нахождения максимальной клики в графе является NP-полной. То есть CLIQUE
a.) в NP и b.) существует NP-полная задача, 3-SAT для одной, которая сводится к CLIQUE за полиномиальное время.
Часть (b) выше в порядке - повсюду в каждом ресурсе и очень хорошо объяснена. Насколько я знаю, для части (а) нам нужно иметь следующее: для конкретного экземпляра решения нам нужно показать, что можно за полиномиальное время проверить, что это решение является ответом на эту проблему. Так, например, учитывая конкретный граф и его подграф, мы должны иметь возможность проверить, является ли этот подграф кликой максимального размера в этом графе.
Ресурсы, которые я читал до сих пор, формулируют эту часть (a) здесь как «простую, прямую и т. д.» или «можно показать за время O (n ^ 2), что данный подграф является кликой или нет». Однако проверка здесь заключается не только в том, является ли это кликой, но и в том, является ли она максимальной кликой в графе. Как это можно решить за полиномиальное время?
Что мне здесь не хватает?
