Yuri Gendelman писал(а):
BorysB писал(а):
2) Огромное количество NP-полных задач.
...едва ли найдется какая-то задача, решение которой окажет такое-же влияние на мир, как решение единственной NP-полной задачи.
Это еще и автоматически докажет, что

.
Ну а если выяснится, что

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

Необходимо еще найти один такой алгоритм (решающий одну NP-полную задачу), а не просто доказать его существование. Но и это не все:
1) степень влияния на мир этого решения будет напрямую зависеть от степени

и коэффициэнта C сложности этого решения

, оттого, насколько они велики,
2) конечно, полиномно решив одну NP-полную задачу можно полиномно решить и остальные, только степени и коэффиценты сложности у них уже будут другие - много больше. Все не так просто.
Yuri Gendelman писал(а):
В полной теории любое истиное высказывание может быть выведено с помощью заданных правил вывода. Теорема Геделя как раз и показывает, что есть неполные теории.
Теория есть некоторое множество логических утверждений, замкнутых относительно всех правил вывода данной логики. Полная теория характеризуется (для бинарной логики с отрицаниями

) тем, что в ней доказуемо любое утверждение или его отрицание.
Противоречивая теория (доказуемо и

и

) с правилом вывода modus ponens также полна, ибо в ней доказуемы
все утверждения. Но есть теории, которые нельзя асиоматизировать конечным числом аксиом, даже более того, бесконечным числом рекурсивно перечислимых аксиом - их существование и утверждает теорема Геделя, точнее она говорит, что
арифметика первого порядка, если она непротиворечива - есть теория рекурсивно не аксиоматизируемая, как и все теории сильнее ее (теории с дополнительными аксиомами, а более обще, теории дающие модель арифметики и, тем самым, доказывающие непротиворечивость последней относительно себя).