Comments 8
Стивен Кук заявил, что кто-нибудь предоставит убедительное доказательство в ближайшие 20 лет.
Как и для фильма "Назад в будущее" в 1985 году казалось, что к 2015 году у нас будут компактные ядерные реакторы и летающие на антиграве автомобили.
Возможно, точно также окажется и с алгоритмами для NP-задач в случае равенства NP и P (к слову, некоторые математики в опросе SIGACT News так и ответили: гипотеза не выводима из существующей системы аксиом, то есть не может быть доказана или опровергнута).
Для остального человечества это будет значить что P!=NP, так как построить такой алгоритм не получится.
Не факт. Невыводимость гипотезы с бытовой точки зрения означает, что вопрос P=NP некорректен и вопрос равенства не абсолютная истина, а зависит от нашей трактовки.
Как с 5 постулатом Евклида. Верен ли он для человечества? Разумеется верен, ну по крайней мере когда мы говорим про геометрию, которая используется в технике и архитектуре и разумеется неверен, когда мы говорим про геометрию в астрономии.
Вопрос не может быть некорректным, он практический. Для бытового применения интересен вопрос "можно ли на традиционном компьютере реализовать идеальный точный алгоритм SAT за полиномиальное время". Все рассуждения про математику, трактовку и истины, расписаны например тут: https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%91%D0%B0%D0%BD%D0%B0%D1%85%D0%B0_%E2%80%94_%D0%A2%D0%B0%D1%80%D1%81%D0%BA%D0%BE%D0%B3%D0%BE . Математически разделить конечно можно, но физического смысла никакого нет.
В практической плоскости выглядит странным утверждение:
Если окажется, что некоторые задачи, для которых, как считалось, не существует эффективных алгоритмов, можно решать быстро, то многие методы защиты устареют.
Погодите, но ведь эти алгоритмы ещё найти надо! Каким образом доказательство равенства классов поможет их найти или затруднит воспрепятствование их поиску? Что мешает уже сейчас попытаться их найти? Утверждение звучит как "мы не знаем, возможно ли это или нет, и даже не пытаемся, но если узнаем, что возможно, то сразу сможем".
Предполагается, что из доказательства можно будет извлечь конкретный алгоритм (то есть, что оно будет "конструктивным"), или хотя бы что оно даст намек на то, как этот алгоритм искать.
Хотя, конечно, в математике бывают существенно неконструктивные доказательства. Обычно они так или иначе полагаются на аксиому выбора.
Вообще говоря это может означать то, что есть какой-то алгоритм, который на практике решает SAT за полиномиальное время, но про который нельзя доказать, что он работает во всех случаях.
Пытаюсь понять, что обозначают аксиомы Блюма... Возьмём задачу "возвращать ноль независимо от входа" - это как раз и будет таким примером задачи, алгоритм для которой можно бесконечно ускорять относительно размера входа? Но это как-то слишком тривиально получается...
История проблемы равенства классов P и NP