"Докажите, что NP-Complete определяет заданные входные данные G и k, имеет ли G как клику размера k, так и независимый набор размера k. Обратите внимание, что это 1 проблема, а не 2; ответ - да тогда и только тогда, когда G имеет оба этих подмножества. "
Мы получили эту проблему в моем курсе алгоритмов, и большая группа студентов не могла ее решить.Вот что мы имеем до сих пор ...
Мы знаем, что как проблемы клики, так и задачи с независимыми множествами сами по себе являются NP-полными.Мы также знаем, что проверка этой проблемы, учитывая некоторый «сертификат», находится в NP.
Проблема заключается в том, чтобы каким-то образом выполнить приведенную выше задачу (которая содержит как независимые множества, так и клики) к любой задаче,полностью из кликов или независимых наборов (по крайней мере, это то, что мы думаем, что должны сделать).Мы не знаем, как выполнить это сокращение без потери информации, необходимой для того, чтобы вернуть сокращение к его первоначальному виду.