Анализ гамильтоновых путей

Question

Мне сказали, что если бы у графа был гамильтонов путь, он не был бы рассчитан за полиномиальное время. Давайте предположим, что мы МОЖЕМ решить это за полиномиальное время, как я могу это доказать? это невозможно, так как это NP трудная проблема?

Answer 1

Задача о гамильтоновом пути является NP-полной.
Никто не доказал, что это невозможно решить за полиномиальное время, но маловероятно, что такое решение существует. Если вам действительно удастся найти его, это означает, что вы доказали P=NP, и Институт математики глины буквально наградит вас за это миллионом долларов:)