?

Log in

p ?= np - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

p ?= np [янв. 4, 2017|07:02 pm]
Anatoly Vorobey
[Tags|, ]

Скотт Ааронсон, на замечательный блог которого я многажды давал ссылки, опубликовал обзорную статью о вопросе P?=NP - главной нерешенной проблеме информатики и одной из главных в математике (хотя не все математики с этим согласятся):

http://www.scottaaronson.com/papers/pnp.pdf

100 страниц текста, не считая библиографии - и лишь малая часть посвящена определениям и базисным вопросам - в основном речь идет о достижениях, перспективах, разных подходах... Текст написан для широкой аудитории "математиков, ученых и инженеров". Для заинтересованных гуманитариев есть другая статья, всего 50 страниц (полцены!) "Почему философов должна интересовать теория сложности". Впрочем, технарям она тоже вполне может показаться интересной:

http://www.scottaaronson.com/papers/philos.pdf

Распечатал обе статьи, потому что вторую хотел перечитать все равно. Если что-то пойму в первой, напишу рецензию отдельно :)
СсылкаОтветить

Comments:
From: (Anonymous)
2017-01-04 07:12 pm
А расскажите для меня, как внешнего наблюдателя, вокруг чего там все на самом деле? (Ну, конечно, если речь всего лишь про complexity classes при использовании ораклов - тады ладно, тады дело всего лишь в том, что для меня P vs NP - немногие из практически реализуемых классов... А если еще что, кроме этого да еще сухого остатка типа проблемы неразрешимости - тогда пожалуйста расскажите!!)
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-01-04 07:26 pm
Ну, даже если говорить о классах, на практике вы наверняка используете и вероятностные вычисления и криптографию, а все это не совсем (а точнее совсем не) про P vs. NP, хотя все эти вопросы так, или иначе связаны с вопросом P vs. NP.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-01-04 10:44 pm
Для меня криптография как раз базируется на верности P!=NP, так что центральным этот вопрос вполне остается. Хотя, конечно же, конкретные криптосхемы - за пределами вопроса.
(Ответить) (Parent) (Thread)
From: 011010011001011
2017-01-04 07:34 pm
Все самое интересное, на мой biased взгляд, происходит в алгоритмах, а не сложности. Например, одна из лучших теоретических работ последнего времени: https://arxiv.org/abs/1307.2205 . Если интересно, могу написать, почему я так думаю.

Еще много совершенно замечательного происходит в криптографии, и это даже сравнительно легко объяснить внешнему наблюдателю.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-01-04 10:46 pm
Спасибо. Да, любые объяснения про взгляд "изнутри" и про то, чем "живет" CS были бы очень интересны!
(Ответить) (Parent) (Thread)
From: 011010011001011
2017-01-05 11:53 am
Ну есть такая задача -- поиск максимального потока (maximum flow problem, на википедии есть приличная статья про нее). Она интересна тем, что это один из очень немногих примеров "транспортных" задач, для которых есть быстрые алгоритмы, которые по этой причине довольно популярны в приложениях*.

Есть "тривиальный" способ найти максимальный поток -- записать очевидную задачу линейного программирования (ЛП) и скормить его солверу, но это работает медленно, и в теории, и на практике. Долгие годы исследователи придумывали комбинаторные алгоритмы, которые были все быстрее и быстрее и дальше и дальше от ЛП.

А потом приходит Александр и показывает, как заточить некий алгоритм для ЛП**, чтобы искать максимальный поток быстрее, чем самый быстрый комбинаторный алгоритм!

Это замечательно по нескольким причинам:

1. Результат -- один из немногих на стыке комбинаторной и непрерывной оптимизации, доказательство очень эклектичное и использует глубокую теорию быстрого решения линейных систем некоторого специального вида.
2. Алгоритм отражает и продолжает тенденцию использовать непрерывную оптимизацию для всего, чего только можно. То есть, классическая оптимизация (градиентный спуск, или тот же interior point method) оказывается крайне полезна для чисто дискретных задач. Это по-моему здорово, так как комбинаторные методы ближе к искусству, а непрерывная оптимизация -- к науке.

* Если встает вопрос, как моделировать ту или иную ситуацию, то логично использовать формулировку, для которой есть более быстрые алгоритмы, даже если она чуть грубее. Например, в computer vision есть алгоритм сегментации изображений на основе максимальных потоков, который по качеству уступают более продвинутым, но, в силу своей быстроты и простоты, он до сих пор крайне популярен, насколько я понимаю.

** Так называемый Interior Point Method.
(Ответить) (Parent) (Thread)
[User Picture]From: lightjedi
2017-01-05 01:41 am
Криптография, к сожалению, достигла той стадии, когда схемы стали слишком сложны для анализа, поиска ошибок, и имплементации без багов. Сложность побеждает безопасность, а должно быть наоборот.

К этому давно шло, за последние 10 лет количество статей выросло втрое, а общий объем наверно впятеро. Сообщество не осиливает такие масштабы.
(Ответить) (Parent) (Thread)
From: 011010011001011
2017-01-05 11:33 am
По-моему, основная проблема прикладной криптографии -- недобросовестность, а не сложность (я не буду показывать пальцем, но есть далеко не один пример, когда авторов нашумевших статей ловили за руку на более-менее подлоге, а они делали вид, что ничего не происходит).

Но вообще, я бы смотрел на ситуацию оптимистично. Сейчас как раз тот момент, когда алгоритмы на основе zero-knowledge proofs становятся из чисто теоретических конструкций практичными (см., например, zcash), и это воодушевляет.
(Ответить) (Parent) (Thread)
[User Picture]From: lightjedi
2017-01-06 01:12 am
Ну так чтобы на подлоге ловили я что-то не припомню (надеюсь, речь не о поливании грязью со стороны Бернштейна). Или речь про Коблица с Менезесом? Но они тоже больше понтов накидали, чем реальные проблемы вскрыли.

Zcash как раз пример очень сложного протокола. Я не уверен, что много людей прочитало и поняло весь протокол начиная с zkSNARKs, не говоря уж про доказательства. Ошибки в таких схемах можно годами искать.

Кстати, zero-knowledge proofs используются издавна - обычные электронные подписи это тоже zero knowledge proof в конце концов:) А вот СНАРКи да, появились недавно, теперь можно доказывать про хэш-функции тоже с zero knowledge. Но это, прямо скажем, не очень часто нужно, да и доказательство готовить - достаточно долго (если не ошибаюсь, речь идет о ключе гигабайтного размера для генерации СНАРКов).
(Ответить) (Parent) (Thread)
From: 011010011001011
2017-01-06 01:16 am
Написал в личку.

И да, я имел ввиду более-менее general-purpose zero-knowledge, а никакие не цифровые подписи.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2017-01-05 07:40 am
Напишите.
(Ответить) (Parent) (Thread)
[User Picture]From: shadow_ru
2017-01-04 07:43 pm
Может в типах, lambda calculus, вычислимости и вот этом вот всём?
(Ответить) (Parent) (Thread)
From: 011010011001011
2017-01-04 07:55 pm
Это все --- так называемая "theory B", я имел ввиду "theory A" (алгоритмы, сложность, криптография). Что происходит в "theory B" --- мне совершенно неведомо.
(Ответить) (Parent) (Thread)