?

Log in

No account? Create an account
P = NP - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

P = NP [21 January 2011|17:31]
Oleg Eterevsky

Пост для математиков и примкнувшим к ним.

В свете недавнего «доказательства» на Хабре того, что P = NP, я тут задался следующим вопросом: а ведь если бы и вправду придумали полиномиальный алгоритм для NP-задач, что бы это означало для математики? Задача поиска доказательства для любой данной теоремы относится к классу NP, ведь коль скоро доказательство приведено (и написано на формальном языке), его проверка вполне возможна за полиномиальное время. Конечно, полином это от длины доказательства, а не от длины утверждения, но всё равно неплохо.

Мораль: если кто-то придумает алгоритм, решающий NP-полную задачу, он сможет претендовать не только на 1000000$ причитающиеся за эту задачу от института Клэя, но и ещё на 5 таких же призов за оставшиеся 5 нерешённых задач. Выгода.

LinkReply

Comments:
From: viktorpetrov
2011-01-21 03:01 pm (UTC)
Ну допустим даже есть алгоритм, находящий доказательство длины N за O(N^2). Теперь оцени размер, скажем, доказательства Уайлса, записанного в виде, пригодном для проверки компьютером, и возведи в квадрат.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 04:02 pm (UTC)
Кстати сказать, объём формальных доказательств не так чтобы слишком велик, так что всё реалистично. Можно и поднапрячься с вычислительными ресурсами. :)
(Reply) (Parent) (Thread)
[User Picture]From: cavaler
2011-01-21 03:12 pm (UTC)
Я так понимаю, что это главным образом будет иметь теоретические последствия. Например, в виде теоретического краха почти всей современной криптографии, там же куча всего завязана на NP.

Практические - далеко не так сильно и не сразу. Полином полиномом - но коэффициенты в нем могут быть до небес.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 04:04 pm (UTC)
Ну дык возможность автоматически доказать или опровергнуть любую теорему — нехилые такие теоретические последствия.
(Reply) (Parent) (Thread)
[User Picture]From: vse_budet
2011-01-21 04:19 pm (UTC)
Во-первых, не любую, а только такую, у которой есть доказательство или опровержение, мне кажется. Во вторых, это и так верно:)
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 04:31 pm (UTC)
Хм. Да, остаётся неопределённость: либо доказательство слишком длинное и мы до него просто ещё не дошли, либо доказательства и опровержения не существует.

А на счёт верно — дык эта, за экспоненциальное время. Долго ждать. :)
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 10:47 pm (UTC)
А когда это время работы учитывалось в разговорах о алгоритмической разрешимости ("возможность автоматически доказать")?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 10:50 pm (UTC)
Ну, например много лет назад когда я слушал спецкурс В.П. Оревкова на эту тему, там время учитывалось. :)
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 11:44 pm (UTC)
Хм... У меня пока (по курсам Н. К. Верещагина и Л. Д. Беклемишева) складывается впечатление, что теория алгоритмов делится на две части - алгоритмическая разрешимость, в которой неважна сложность, и теория сложности, в которой алгоритмическая разрешимость очевидна.
Впрочем, это все лирика)
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 11:56 pm (UTC)
А понял. Я имел в виду автоматический поиск доказательств. Там на время смотрят. В той теории где про разрешимость вообще говорят, время действительно особо не учитывается.
(Reply) (Parent) (Thread)
[User Picture]From: cavaler
2011-01-21 06:53 pm (UTC)
Так никто не сказал, что будет _практическая_ возможность:
1. См. выше, коэффициенты у полиномов.
2. Доказательство того, что P == NP, не обязательно влечет за собой готовый алгоритм, как NP превратить в P, а только знание того, что такое возможно.
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-22 07:28 am (UTC)
2. Обязательно: можно "параллельно" запустить все возможные алгоритмы, проверяя в конце каждого корректность выполняющего набора. Для выполнимых формул сработает за полиномиальное время [Левин, ...дцать лет назад].
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-21 04:57 pm (UTC)
А главное, они будут неожиданно падать на голову!

(Свиньи, которые будут летать :) )

Что полином таки от длины доказательства, это тоже "печально". Которое может иметь потенциально совершенно какую угодно длину. Причём в слегка другой системе доказательств оно будет иметь совершенно другую длину.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:21 pm (UTC)
То есть простор для творчества у математиков всё-таки будет: выдумывать более оптимальные системы доказательств.
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-21 05:36 pm (UTC)
Я бы на их месте лучше почаще на небо смотрел :)
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 07:24 pm (UTC)
Мне кажется, что в оптимальной алгоритмически проверяемой системе доказательств длина доказательства утверждения A будет примерно равна min({KS(t), t>=X(A)}), где X(A) - длина кратчайшего классического доказательства A.
Правда, очевидным способом мы так получим только одностороннюю проверяемость (по корректному доказательству скажем, что оно корректно). Как быть с обратным - не очень понятно.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 05:13 pm (UTC)
Полиномы бывают очень разные. Даже сотая степень от длины доказательства - это уже очень печально. А может быть и во много раз больше.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:18 pm (UTC)
Нет, ну положа руку на сердце, много ли мы знаем алгоритмов медленнее n^4?
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 05:25 pm (UTC)
Ну например AKS - работает за n^6.
Кроме того, алгоритмов, решающих NP-полную задачу за полиномиальное время мы знаем меньше.
И, кроме того, есть задача, которую нельзя сделать за n^4, но можно за n^9 (например).
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:43 pm (UTC)
Вообще, да. Полиномиальный алгоритм для NP-полной задачи должен основываться на каких-то совершенно неизвестных нам принципах, так что он может сильно отличаться от всего что нам известно, и действительно иметь большую степень.
(Reply) (Parent) (Thread)
[User Picture]From: dmitrits
2011-01-21 05:27 pm (UTC)
Найти доказательство одного доказуемого утверждения можно за константное время: перебирать все строчки и проверять, являются ли они доказательствами. Если даже для SAT будет алгоритм, работающий Cn^2, где C=2^300, то о практике речь уже идти не будет.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:42 pm (UTC)
Я ж не говорю о поиске доказательства конкретной теоремы. Я говорю об общем алгоритме.
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-22 07:27 am (UTC)
Ну вот "самая надёжная криптосистема с открытым ключом" есть. Помогло это кому-нибудь на практике? :)
(Reply) (Parent) (Thread)
From: ajtkulov
2011-01-21 07:03 pm (UTC)
А точно ли, что все остальные задачи (со стоимостью 10^6) лежат в NP?
Такое ощущение, что все интересное начинается с NEXPTIME и выше, а там все плохо даже если окажется равенство между P и NP...
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 07:23 pm (UTC)
Это ж не алгоритмические задачи, а математические. Какой тут NEXP?
(Reply) (Parent) (Thread)
From: ajtkulov
2011-01-21 09:09 pm (UTC)
доказательство в теориях с ограниченными кванторами (ограниченная арифметика, ограниченная теория слов) сложнее чем 3-SAT и лежит в NEXP*
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 10:41 pm (UTC)
Может быть это из-за того, что мы отталкиваемся от длины формулировки, а не от длины доказательства? Формально говоря, задача, лежащая в NP звучит так:

Верно ли, что существует доказательство (или опровержение) утверждения a длиной не более n символов?
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 10:45 pm (UTC)
И почему эта задача в NP?
Можно задать последовательность утверждений, длина доказательств которых растет экспоненциально по длине формулировки. Так что доказательство в качестве подсказки не подойдет. Есть какой-то другой способ?
В NP точно лежит такая задача: существует ли доказательство утверждения длиной не более чем данное слово?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 10:48 pm (UTC)
Оно в NP если взять n в качестве параметра. Правда, я тут действительно задумался о том, что негативный результат (отсутствие доказательства) мы не сможем проверить...
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 10:58 pm (UTC)
То есть времени работы/длине подсказки разрешаем быть экспонентой от n? Тогда да, все хорошо.

А вот задача отсутствия доказательства алгоритмически неразрешима, т.к. иначе множество доказуемых формул разрешимо. Соответственно, множество опровержимых формул разрешимо. Тогда возьмем эффективно аксиоматизируемую теорию, содержащую PA, по следующему правилу. Будем перебирать все формулы в лексикографическом порядке. Если очередная формула не опровергается уже взятыми аксиомами, то добавим ее в список аксиом. Получим эффективно аксиоматизируемую теорию, содержащую PA, равнонепротиворечивую с PA, в которой всякая формула либо доказуема, либо опровержима - возьмем какую-нибудь формулу, она либо опровергается аксиоматическими формулами, идущими перед ней, либо сама является аксиомой. По теореме Геделя получаем, что наша теория, а вместе с ней и PA противоречива. Печально.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 11:29 pm (UTC)
n — это ограничение на длину доказательства, а не длина утверждения, так что полином от него, а не экспонента.

А задача, которую я написал — безусловно разрешима, так как можно просто перебрать все доказательства длины n.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 11:41 pm (UTC)
Если n - ограничение на длину доказательства, то длина доказательства есть экспонента от длины n.
Язык из NP, если есть алгоритм, такой что для всякого слова из языка есть подсказка полиномиальной длины, такая что пара "слово+подсказка" принимается алгоритмом за полиномиальное время (ну и для слов не из языка подсказок нет).
Если слово - это пара "утверждение, длина доказательства" то длина доказательства может оказаться экспонентой от длины слова, т.е. доказательство в качестве подсказки не подходит.

Отсутствие доказательства длины меньше n, разумеется, разрешимо. Но вряд ли можно показать, что оно в NP. Если бы это было так, то задача о существовании доказательства длины меньшей n была бы из co-NP. А так как эта задача NP-полна (вроде), то получили бы, что NP \subseteq co-NP.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 11:55 pm (UTC)
> Если n - ограничение на длину доказательства, то длина доказательства есть экспонента от длины n.

А, я понял в чём вопрос. Формально говоря, класс NP определяется в зависимости от длины ввода. А длина n — это как бы log n. В таком случае, когда всем понятно, что хочется ассимптотику от n, а не от длины, делают так: считают, что число n записано на машине Тюринга в виде n единичек. То есть длина ввода тоже получилась n.

Но это всё казуистика. Меня другое интересует. Вот предположим, что у нас есть задача такая, что позитивный ответ мы у неё можем проверить за полином, а негативный — не можем. Верно ли, что при условии что P = NP, для такой задачи существует алгоритм, который в случае позитивного ответа выдаёт его за полиномиальное время, а в случае негативного, скажем, не заканчивает работать?

Если это верно, то мы можем построить доказательство для любой _решаемой_ теоремы за полиномиальное время следующим образом. Запускаем наш алгоритм для n = 2, потом через секунду параллельно для n = 4, потом через 2 секунды для n = 8, потом через 4 секунды для n = 16 и т.д. Я сейчас слишком сонный чтобы считать, но помоему так мы гарантированно получим доказательство за полиномиальное время от его длины (если оно существует).
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-22 12:06 am (UTC)
Про унарную запись как-то не подумал. Спасибо, буду знать.

Если P = NP, то вся начальная часть полиномиальное иерархии схлопывается. В частности, если P=NP, то co-P = co-NP, а посколько P = co-P, то co-NP = P. Если позитивный ответ мы можем проверить за полином и P=NP, то за полином мы можем найти этот ответ, если он есть (стандартным приемом), или сказать, что его нет (это задача из co-NP).
Поскольку при двоичном подъеме мы на промежуточных шагах проделываем в худшем случае полиномиальный объем работы от последнего шага - то да, мы сможем найти доказательство за полином от его длины.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-22 02:25 am (UTC)
Перечитал еще раз.
Если P=NP, то для всякой задачи, для которой мы можем проверить ответ за полином, мы можем и сказать, существует ли он, за полином.
(Reply) (Parent) (Thread)
[User Picture]From: ted_dy
2011-01-21 08:25 pm (UTC)
Что-то я не понял... это всё при условии, что решение есть...
(Reply) (Thread)
[User Picture]From: mihaild
2011-01-21 09:33 pm (UTC)
Это при условии, что не только решение существует, но и кто-то его найдет.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 10:42 pm (UTC)
Не-не, если P=NP, то находить его не надо — оно само найдётся.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 10:48 pm (UTC)
То есть?
Пусть кто-то найдет неконструктивное доказательство того, что P=NP. Чем это поможет в решении остальных проблем?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-21 10:49 pm (UTC)
А, да, естественно. Подойдёт только конструктивное доказательство.
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-22 07:24 am (UTC)
Его уже Левин ...дцать лет назад нашёл :) Оптимальный алгоритм для SAT называется. Если P=NP, то он полиномиальный, когда решение есть. Правда, если доказательство настолько неконструктивно, что и полином не оценить, то для UNSAT это ничего не даст.
(Reply) (Parent) (Thread)
[User Picture]From: edwardahirsch
2011-01-22 07:25 am (UTC)
Для выполнимых формул автоматически получается конкретный (хоть и не практический) полиномиальный алгоритм. Собственно, мы его даже знаем (оптимальный алгоритм Левина, который все параллельно запускает), осталось доказать P=NP :)
(Reply) (Parent) (Thread)