Напомним, что полный подграф неориентированного графа G=(V, E) – это граф G/=(V/, E/), для которого V/ Í V, E/ Í E, и между каждой парой вершин из E/ существует ребро в V/.
Для доказательства теоремы 2 используется теорема 1.
Теорема 1. Задача о выполнимости булевой формулы является NP -полной.
Теорема 2. Задача, определения того, содержит ли неориентированный граф G=(V, E) полный подграф с k вершинами, является NP -полной.
Доказательство. Опишем недетерминированный полиномиальный алгоритм для определения того, содержит ли G полный подграф с k вершинами. Алгоритм недетерминировано выбирает подмножество из k вершин и проверяет за время O(k2), является ли оно полным. Этим доказано, что задача входит в класс NP. Теперь мы должны доказать, что задача является NP -трудной; мы сделаем это показав, что в нее преобразуется задача выполнимости булевой формулы.
Предположим, что дано булево выражение С1 Ù С2 Ù … Ù Сk, представленное в конъюнктивной нормальной форме, где каждое Сi является дизъюнктом. Преобразуем вопрос о его выполнимости в вопрос существования полного подграфа с k вершинами в графе, который можно построить из данного выражения за время, полиномиальное относительно его длины. Рассмотрим неориентированный граф G=(V, E), определяемый следующим образом:
V={(a, i)| a - литерал в дизъюнкте Сi },
E={((a, i), (b, j))| i ¹ j и a ¹ b}.
Интуитивно ясно, что для каждого вхождения литерала в выражение графа G имеет вершину и ребра соединяют такие пары литералов из различных дизъюнктов, которым можно одновременно придать значение истинно. Полный подграф с k (число дизъюнктов) вершинами в G соответствует k литералам из разных дизъюнктов, которым одновременно можно придать значение истинно так, что литералы, дизъюнкты и отсюда само выражение имеют значение истинно. таким образом выражение является выполнимым, если G содержит полный подграф с k вершинами. Обратно, если выражение является выполнимым, то существует распределение значений истинно и ложно по переменным, такое, что выражение истинно. Иначе говоря, каждый из k дизъюнктов содержит литерал, значение которого есть истинно, и вершины, соответствующие этим буквам, образуют полный подграф с k вершинами. Таким образом, граф G=(V, E) содержит полный подграф с k вершинами, если и только если выражение является выполнимым. Очевидно, G можно построить по выражению за полиномиальное время.
Необычное свойство недетерминированных алгоритмов — различная сложность задачи разрешения и её дополнения. Практическое значение определения принадлежности задачи классу сложности
Рассмотрим задачи разрешения, ответами в которых являются просто «да» или «нет». Определим дополнение такой задачи Р как задачу 
, в которой ответы обратны.
Пример. Р: «Является ли данная булева формула выполнимой?»,
: « Является ли данная булева формула невыполнимой?»
Если существует детерминированный полиномиальный алгоритм для Р, то простым отрицанием выхода мы получаем детерминированный полиномиальный алгоритм для . Таким образом, РÎP тогда и только тогда, когда Î P. Для NP такой результат неизвестен, а именно: неизвестно, что существование недетерминированного полиномиального алгоритма для задачи Р гарантирует существование такого алгоритма для .
Тот факт, что задача разрешения и её дополнение могут быть неодинаковой сложности, противоречит нашему интуитивному представлению. Трудность здесь проистекает из необычной природы недетерминированного вычисления: ответ «да» должен соответствовать оператору успех и мы не можем просто взять дополнение к выходу недетерминированного алгоритма, поменяв местами успех и неудача, поскольку окончательный успех требует только одного успешного пути вычислений, в то время как окончательная неудача требует чтобы все пути вычисления вели к неудаче. Это означает, что недетерминированное вычисление более приспособлено для задачи существования типа «существует ли элемент х, такой, что некоторое свойство для него выполняется?», чем для дополнительных к ним задач несуществования типа «выполняется ли некоторое свойство для всех х?».
Доказано, что для любой NP -полной задачи P дополнение 
Î NP тогда и только тогда, когда класс NP замкнут относительно дополнения.
Понятие NP -полноты первоначально возникло в связи с попытками доказать гипотезу P ¹ NP. Если это так, то NP -полные задачи лежат в разности NP\ P. В настоящее время известно много примеров NP -полных задач, но ни про одну из них не удалось доказать, что она лежит в классе P. Сейчас характеризация задачи как NP -полной (NP -трудной) воспринимается как довод в пользу невозможности ее практического решения программными средствами в столь общей постановке, т.е. написать программу на всех исходных данных не удается. Выходом является сужение задачи, переход к частным случаям, на которых программа работает эффективно.