Я нашел в Интернете алгоритм полиномиального времени для раскраски графа, возможно, доказывающий P=NP

Question

Я искал алгоритмы раскраски графа и нашел алгоритм, который, как утверждает автор, работает за полиномиальное время. Автор приводит также исходный код программы C++ и демонстрационную программу.

Подозрительным является то, что проблема решения, является ли граф k-раскрашиваемым, является NP-полной, поэтому не должно быть никакого алгоритма полиномиального времени, пока P=NP.

Однако автор не утверждает, что алгоритм работает для всех графов, он лишь говорит, что не нашел ни одного графа, для которого алгоритм не работает.

Итак, вопрос: действительно ли этот алгоритм работает для каждого графа, а это означает, что на самом деле P=NP, или существуют определенные графы / классы графов, для которых он не работает? А может, в расчете сложности просто ошибка?

Answer 1

Я думаю, что вы не очень внимательно прочитали тезисы.

Автор представляет алгоритм, который находит m-краски графа, для некоторых m меньше предела, налагаемого теоремой Брукса: https://en.wikipedia.org/wiki/Brooks'_theorem

(который старый и утверждает, что chi < delta + 1 как утверждает автор во втором предложении.)

Автору известен вопрос P vs NP. Газета не претендует на решение вопроса, он просто заявляет:

Для всех известных примеров графов алгоритм находит правильную m-раскраску вершин графа G для m, равного хроматическому числу χ(G)

Затем он спрашивает,

Ввиду важности вопроса P против NP, мы спрашиваем: существует ли граф G, для которого этот алгоритм не может найти правильную m-раскраску вершин G с m, равным хроматическому числу χ(G)?

Акцент в оригинале (!)

Таким образом, он не претендует на то, чтобы разрешить P против NP, просто, в рамках академического исследования, они спрашивают: "Может ли кто-нибудь привести пример, на котором этот алгоритм не может достичь хроматического числа", что может быть полезно для математического анализа? цели. Крайне маловероятно, что алгоритм фактически достигает хроматического числа для всех графиков. (Хотя с научной точки зрения неизвестно, делает это или нет.)