Является ли дополнение языка CLIQUE элементом NP?
Я изучаю класс NP и один из слайдов упоминает:
It seems that verifying that something is not present is more difficult than verifying that it is present.
______ _________
Hence, CLIQUE (complement) and SubsetSUM (complement) are not obviously members of NP.
Было ли когда-либо доказано, является ли дополнение CLIQUE элементом NP?
Кроме того, у вас есть доказательства?
2 ответа
На самом деле это открытая проблема! Класс сложности co-NP состоит из дополнений всех задач в NP. Неизвестно, является ли NP = co-NP прямо сейчас, и многие люди подозревают, что ответ отрицательный.
Так же, как CLIQUE является NP- завершенным, дополнение CLIQUE является co-NP- полным. (В более общем случае, дополнением к любой NP- полной проблеме является совместная NP- полная). Существует теорема, что если в NP есть какая - либо неполная проблема, связанная с NP, то co-NP = NP, что станет огромным теоретическим прорывом.
Если вы хотите узнать больше об этом, ознакомьтесь со статьей в Википедии о co-NP и поищите в Интернете другие ресурсы.
Общая интуиция здесь: легко доказать, что граф содержит N-клику: просто покажи мне клику. Трудно доказать, что граф, у которого нет N-клики, фактически не имеет N-клики. Какое свойство графа вы собираетесь использовать для этого?
Конечно, для некоторых семейств графов вы можете - например, графы с достаточным количеством ребер не могут иметь такую клику. Вполне возможно, что все графы могут иметь похожие доказательства, построенные вокруг них, хотя это было бы удивительно - почти так же удивительно, как P=NP.
Вот почему дополнение языков в NP, в общем, явно не в NP - фактически, у нас есть термин "co-NP" (как в "дополнении в NP") для обозначения таких языков, как!CLIQUE,
Один из распространенных подходов к достижению прогресса в теории сложности, когда мы не добились прогресса по сложным вопросам, - это показать, что какой-то конкретный трудно доказываемый результат подразумевает нечто удивительное. Показано, что NP=co-NP является общей целью этих доказательств - например, любая сложная проблема как в NP, так и в co-NP, вероятно, не завершена ни для одного, потому что, если бы она была завершена для обоих, и, следовательно, оба равно, так что у вас есть те сумасшедшие общие графические доказательства.
Это даже обобщает - вы можете начать говорить о том, что произойдет, если у ваших NTM (или контролеров сертификатов) есть оракул для законченного языка NP, такого как CLIQUE. Очевидно, что и CLIQUE, и!CLIQUE находятся в P^CLIQUE, но теперь есть (возможно) новые языки в NP^CLIQUE и co-NP^CLIQUE, и вы можете продолжать идти дальше, пока у вас не будет полной иерархии классов сложности - "полиномиальная иерархия". Эта иерархия интуитивно продолжается вечно, но может в какой-то момент разрушиться или вообще не существовать (если P=NP).
Полиномиальная иерархия делает эту общую методику аргументов более мощной - показ того, что некоторый результат приведет к коллапсу полиномиальной иерархии до 2-го или 3-го уровня, сделает этот результат довольно удивительным. Даже показ того, что это рушится вообще, было бы несколько удивительно.