Прежде всего, мое понимание теоремы Гёделя о неполноте (и формальной логики в целом) очень наивно, а также мои знания в области теоретической информатики (имеется в виду только один выпускной курс, когда я еще студент), поэтому этот вопрос может быть очень наивно
Насколько я мог найти, доказуемость P против NP является открытой проблемой.
Теперь:
- Первая теорема Гёделя о неполноте гласит, что могут быть утверждения, которые являются истинными, но не доказуемыми и не опровергаемыми.
- Если для NP-полной задачи найдено полиномиальное решение, это доказывает, что P = NP.
Итак, предположим, что P = NP недоказуемо:
это означает, что не может быть найдено ни одного примера полиномиального решения для NP-полной задачи (в противном случае это было бы доказательством).
Но если не найден пример полиномиального решения для NP-полной задачи, это означает, что P = NP ложно (доказывая это, то есть утверждение доказуемо), что приводит к противоречию, поэтому P = NP должно быть доказуемо. ,
Это звучит как доказательство доказуемости P = NP для меня, но я думаю, что очень вероятно, что это из-за моего непонимания логических тем. Может ли кто-нибудь помочь мне понять, что не так с этим?
источник
Ответы:
Если P = NP, должны быть алгоритмы полиномиального времени для NP-полных задач. Однако, возможно, не существует какого-либо алгоритма, который доказуемо решает NP-полную проблему и доказанно работает за полиномиальное время.
источник
Теорема Гёделя о неполноте на самом деле о доказуемости, учитывая теорию, обладающую достаточной выразительной силой, в результате вы получите некое утверждение, которое может быть верным в некоторых моделях и ложным в других, а следовательно, недоказуемым. В этом случае, если P против NP не может быть доказано, если вы считаете, что реальность является моделью математики, P = NP или P NP все равно должны быть верны в «нашем мире». Следовательно, как сказал Дэвид, либо полиномиального алгоритма не существует, но мы не сможем доказать это утверждение, либо полиномиальный алгоритм существует, но мы не сможем доказать, что он решает проблему или работает за полиномиальное время. ,≠
источник