Во-первых, почему именно за O(n)? O(n) — это линейное время, а для класса NP речь идет о проверке за полиномиальное время. Теперь собственно о проверке решения задачи о коммивояжере. Дело в том, что эту задачу можно сформулировать разными способами. Первый способ — как распознавательную задачу (decision problem), дающую ответ «да» или «нет». При таком подходе задача о коммивояжере формулируется так: «для заданного количества городов и стоимостей передвижения между городами определить, имеется ли путь проходящий хотя бы единожды по каждому городу, общей стоимостью меньше S». При такой формулировке задача принадлежит к классу NP-complete. Проверить решение легко, складываем стоимости передвижения для всего найденного маршрута и убеждаемся, что сумма меньше S.
Альтернативная формулировка задачи звучит так: «для заданного количества городов и стоимостей передвижения между городами, найти путь проходящий хотя бы единожды по каждому городу и имеющий минимальную суммарную стоимость». Скорее всего вы думали о задаче именно в такой формулировке. К сожалению такая задача относится к классу NP-hard (который не рассматривался в статье), а не к NP. Для задач в классе NP-hard не существует алгоритмов способных проверить решение за полиномиальное время.
«в 94» звучит как возраст Уайлса на момент когда он доказал теорему, потому что в предыдущем абзаце вы говорили как раз о возрасте :) А в целом, книгу читал, увлекательно, хотя конечно очень специфично и посему на любителя.
Само собой. Хотя ученые в большинстве своем люди идейные, но ничто человеческое им не чуждо. А хлеб всем охота не только с маслом, но и желательно с колбасой.
Таблица может и приснилась, но до этого я уверен он не один год ломал себе голову над тем как же упорядочить все известные на тот момент химические элементы.
Я бы все-таки порекомендовал Вам прочитать мою статью, я старался писать ее в научно-популярной форме, насколько это вообще возможно простым языком, приводя простые примеры. Спасибо Вам за веру в меня, но боюсь что для того чтобы доказать или опровергнуть P=NP нужно долгое время профессионально заниматься узкой областью теории алгоритмов. У меня к сожалению немного другое направление. Хотя, конечно миллион долларов — это заманчиво. :)
Альтернативная формулировка задачи звучит так: «для заданного количества городов и стоимостей передвижения между городами, найти путь проходящий хотя бы единожды по каждому городу и имеющий минимальную суммарную стоимость». Скорее всего вы думали о задаче именно в такой формулировке. К сожалению такая задача относится к классу NP-hard (который не рассматривался в статье), а не к NP. Для задач в классе NP-hard не существует алгоритмов способных проверить решение за полиномиальное время.