Почему решение задачи клики не м.б. полиномиальным. Гипотеза

[0101]

Существует оптимальный алгоритм вычисления количества клик заданного размера k в произвольном графе G.
С помощью этого алгоритма можно решить задачу о существовании в заданном графе G клики размера k за количество шагов, не превышающих число вершин графа G. Если с ростом k сложность реализации вышеупомянутого алгоритма растет экспонециально, то решение задачи клики не может быть полиномиальным.

Соображения по поводу оптимального алгоритма.
Будем искать в графе количество клик размером 3. Если сложить значения элементов главной диагонали возведенной в куб матрицы смежности заданного графа и поделить на 6, получим искомое. Эту идею можно обобщить для нечетных клик. Если можем получить количество клик для нечетного k, то получение количества клик для k-1 ненамного сложнее. Для заданного нечетного k нужно решать некоторую систему линейных уравнений, количество неизвестных в которой превышает число видов Эйлеровых графов P, которые можно построить из k(k-1)/2 ребер.
Число P растет экспоненциально в зависимости от k. Поэтому решение задачи клики не может быть полиномиальным.

[0101]

0101 в сообщении #285446 писал(а):

С помощью этого алгоритма можно решить задачу о существовании в заданном графе G клики размера k за количество шагов, не превышающих число вершин графа G.

Это лишнее. Вместо этого нужно было написать, что с помощью этого алгоритма можно найти клику размера k при условии ее существовании в заданном графе G за количество шагов, не превышающих число вершин графа G.

[Xaositect]

0101 в сообщении #285446 писал(а):

Если с ростом k сложность реализации вышеупомянутого алгоритма растет экспонециально, то решение задачи клики не может быть полиномиальным.

Почему? Может быть, для того, чтобы узнать, есть клика или нет, не обязательно считать их все.

[Zealint]

А вы читали книгу Гэри и Джонсона "вычислительные машины и труднорешаемые задачи"? Там есть полное доказательство NP полноты этой задачи.

Что касается вашего рассуждения, вы нигде не обосновали, что для нечётного k вам НАДО (и никак иначе нельзя) рассматривать систему уравнений. Это не доказательство, так как вы оставили возможность существования иного способа вычисления. Надо сначала доказать, что другого не существует.

[0101]

Xaositect в сообщении #286026 писал(а):

Почему? Может быть, для того, чтобы узнать, есть клика или нет, не обязательно считать их все.

Логично. Гипотеза имеет смысл, если доказать, что для того, чтобы узнать, есть клика или нет, считать их все обязательно. По этому вопросу у меня пока соображений нет.

Zealint в сообщении #286027 писал(а):

А вы читали книгу Гэри и Джонсона "вычислительные машины и труднорешаемые задачи"? Там есть полное доказательство NP полноты этой задачи.
Что касается вашего рассуждения, вы нигде не обосновали, что для нечётного k вам НАДО (и никак иначе нельзя) рассматривать систему уравнений. Это не доказательство, так как вы оставили возможность существования иного способа вычисления. Надо сначала доказать, что другого не существует.

Ну это же идея, эскиз Алгоритм для рассчета количества 3-х узловый клик вполне эффективен. Правда, его описание нуждается в исправлении. В начале возводим в квадрат матрицу смежности, в полученной матрице обнуляем главную диагональ, затем уже эту матрицу умножаем вновь на матрицу смежности. Элементы главной диагонали результата – количества клик для соотв. узлов , умноженные на 2. Если их просуммировать - получ. сумма всех клик умнож. на 6. Для получения конкретного алгоритма количества 5 узловых клик, где уже понятно, зачем здесь нужна система уравнений, пока мотивации не хватило, очень уж громоздко. Кстати сказать, если найдется способ сократить количество неизвестных, то алгоритм вполне может оказаться полиномиальным.

[Zealint]

0101 в сообщении #286171 писал(а):

Кстати сказать, если найдется способ сократить количество неизвестных, то алгоритм вполне может оказаться полиномиальным.

В том-то и дело, что не может. Доказано, что на вычислительной машине подобной то, что вы сейчас пользуетесь, алгоритм решения этой задачи в принципе не может быть полиномиальным. Конечно, есть гипотеза о том, что P=NP, но пока никто не привёл пример. Я как раз тоже занимаюсь такого рода задачами, но тоже существенных результатов преодоления NP-полноты не добился.

[Xaositect]

Zealint в сообщении #286240 писал(а):

В том-то и дело, что не может. Доказано, что на вычислительной машине подобной то, что вы сейчас пользуетесь, алгоритм решения этой задачи в принципе не может быть полиномиальным. Конечно, есть гипотеза о том, что P=NP, но пока никто не привёл пример. Я как раз тоже занимаюсь такого рода задачами, но тоже существенных результатов преодоления NP-полноты не добился.

В том то и дело, что не доказано. Много кто в это верит, но все-таки не доказано.

-- Пн фев 08, 2010 23:47:24 --

0101 в сообщении #286171 писал(а):

Логично. Гипотеза имеет смысл, если доказать, что для того, чтобы узнать, есть клика или нет, считать их все обязательно. По этому вопросу у меня пока соображений нет.

Это и есть основной вопрос. Проблема перебора.

[0101]

Xaositect
Вы где-нибудь что-то похожее видели? Если применение этой идеи позволяет находить максимальные паросочетания с полиномиальной сложностью, то она может быть перспективной.

[Xaositect]

0101 в сообщении #287651 писал(а):

Вы где-нибудь что-то похожее видели? Если применение этой идеи позволяет находить максимальные паросочетания с полиномиальной сложностью, то она может быть перспективной.

Что именно?
Вы вроде раньше ничего не говорили о паросочетаниях.

Сам я графовыми алгоритмами интересуюсь мало, но то, что количество клик заданного размера можно найти манипуляциями с матрицей смежности, достаточно очевидно. В википедии, в статье http://en.wikipedia.org/wiki/Clique_problem, есть ссылки на статьи, в которых используется этот прием, напр. http://dml.cz/dmlcz/106381.

[0101]

Идея на счет паросочетаний появилась близко к моменту задания вопроса. Сейчас в процессе проверки. На счет очевидности манипуляций с матрицей смежности Вы подтверждаете мои предположения. Спасибо!

[0101]

0101 в сообщении #287651 писал(а):

Xaositect
Вы где-нибудь что-то похожее видели? Если применение этой идеи позволяет находить максимальные паросочетания с полиномиальной сложностью, то она может быть перспективной.

Это мне написать надо было не про максимальные паросочетания, для которых есть полиномиальный алгоритм, а про количество паросочетаний, которое #P.
Аналогично индексу Hosoya. Если бы был полиномиальный алгоритм, тогда для получения количества 4-х, 6-ти и других четномерных сочетаний был бы полиномиальный алгоритм.

[Zealint]

Xaositect в сообщении #286615 писал(а):

В том то и дело, что не доказано. Много кто в это верит, но все-таки не доказано.

В одной из статей Тарьяна (вроде бы за 73 или 77 год, не помню точно) есть доказательство. Уверен, что автор темы нейдёт, если захочет. Кто-то из специалистов в этой области даже подсказал мне название: "Complexity of Combinatorial Algorithms", но я, опять же, не проверял лично.

[Xaositect]

Zealint в сообщении #291018 писал(а):

"Complexity of Combinatorial Algorithms"

"Complexity of Combinatorial Algorithms" - это обзор. Ничго похожего я в нем не нашел, есть только пара замечаний типа "[...] no one has yet discovered substantially faster algorithm for this problem".