![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaСкотт Ааронсон, на замечательный блог которого я многажды давал ссылки, опубликовал обзорную статью о вопросе P?=NP - главной нерешенной проблеме информатики и одной из главных в математике (хотя не все математики с этим согласятся):
http://www.scottaaronson.com/papers/pnp.pdf
100 страниц текста, не считая библиографии - и лишь малая часть посвящена определениям и базисным вопросам - в основном речь идет о достижениях, перспективах, разных подходах... Текст написан для широкой аудитории "математиков, ученых и инженеров". Для заинтересованных гуманитариев есть другая статья, всего 50 страниц (полцены!) "Почему философов должна интересовать теория сложности". Впрочем, технарям она тоже вполне может показаться интересной:
http://www.scottaaronson.com/papers/philos.pdf
Распечатал обе статьи, потому что вторую хотел перечитать все равно. Если что-то пойму в первой, напишу рецензию отдельно :)
http://www.scottaaronson.com/papers/pnp.pdf
100 страниц текста, не считая библиографии - и лишь малая часть посвящена определениям и базисным вопросам - в основном речь идет о достижениях, перспективах, разных подходах... Текст написан для широкой аудитории "математиков, ученых и инженеров". Для заинтересованных гуманитариев есть другая статья, всего 50 страниц (полцены!) "Почему философов должна интересовать теория сложности". Впрочем, технарям она тоже вполне может показаться интересной:
http://www.scottaaronson.com/papers/philos.pdf
Распечатал обе статьи, потому что вторую хотел перечитать все равно. Если что-то пойму в первой, напишу рецензию отдельно :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2017-01-04 05:20 pm (UTC)no subject
Date: 2017-01-04 05:34 pm (UTC)no subject
Date: 2017-01-04 05:58 pm (UTC)no subject
Date: 2017-01-04 07:05 pm (UTC)no subject
Date: 2017-01-04 07:12 pm (UTC)no subject
Date: 2017-01-04 07:26 pm (UTC)no subject
Date: 2017-01-04 07:32 pm (UTC)no subject
Date: 2017-01-04 07:34 pm (UTC)Еще много совершенно замечательного происходит в криптографии, и это даже сравнительно легко объяснить внешнему наблюдателю.
no subject
Date: 2017-01-04 07:43 pm (UTC)no subject
Date: 2017-01-04 07:55 pm (UTC)no subject
Date: 2017-01-04 08:42 pm (UTC)no subject
Date: 2017-01-04 08:47 pm (UTC)ну если малоприятно, то не надо... однако я знаю нескольких не получивших но перешедших. и потом получивших... но это не жизнь, конечно, не жизнь...
no subject
Date: 2017-01-04 08:56 pm (UTC)no subject
Date: 2017-01-04 09:33 pm (UTC)no subject
Date: 2017-01-04 10:44 pm (UTC)no subject
Date: 2017-01-04 10:46 pm (UTC)no subject
Date: 2017-01-05 01:41 am (UTC)К этому давно шло, за последние 10 лет количество статей выросло втрое, а общий объем наверно впятеро. Сообщество не осиливает такие масштабы.
no subject
Date: 2017-01-05 07:40 am (UTC)no subject
Date: 2017-01-05 07:41 am (UTC)no subject
Date: 2017-01-05 10:05 am (UTC)no subject
Date: 2017-01-05 11:33 am (UTC)Но вообще, я бы смотрел на ситуацию оптимистично. Сейчас как раз тот момент, когда алгоритмы на основе zero-knowledge proofs становятся из чисто теоретических конструкций практичными (см., например, zcash), и это воодушевляет.
no subject
Date: 2017-01-05 11:53 am (UTC)Есть "тривиальный" способ найти максимальный поток -- записать очевидную задачу линейного программирования (ЛП) и скормить его солверу, но это работает медленно, и в теории, и на практике. Долгие годы исследователи придумывали комбинаторные алгоритмы, которые были все быстрее и быстрее и дальше и дальше от ЛП.
А потом приходит Александр и показывает, как заточить некий алгоритм для ЛП**, чтобы искать максимальный поток быстрее, чем самый быстрый комбинаторный алгоритм!
Это замечательно по нескольким причинам:
1. Результат -- один из немногих на стыке комбинаторной и непрерывной оптимизации, доказательство очень эклектичное и использует глубокую теорию быстрого решения линейных систем некоторого специального вида.
2. Алгоритм отражает и продолжает тенденцию использовать непрерывную оптимизацию для всего, чего только можно. То есть, классическая оптимизация (градиентный спуск, или тот же interior point method) оказывается крайне полезна для чисто дискретных задач. Это по-моему здорово, так как комбинаторные методы ближе к искусству, а непрерывная оптимизация -- к науке.
* Если встает вопрос, как моделировать ту или иную ситуацию, то логично использовать формулировку, для которой есть более быстрые алгоритмы, даже если она чуть грубее. Например, в computer vision есть алгоритм сегментации изображений на основе максимальных потоков, который по качеству уступают более продвинутым, но, в силу своей быстроты и простоты, он до сих пор крайне популярен, насколько я понимаю.
** Так называемый Interior Point Method.
P=NP
Date: 2017-01-05 02:41 pm (UTC)Albert
no subject
Date: 2017-01-05 07:08 pm (UTC)no subject
Date: 2017-01-05 08:27 pm (UTC)no subject
Date: 2017-01-05 08:30 pm (UTC)Re: P=NP
Date: 2017-01-05 09:05 pm (UTC)Картинки напоминают Кодекс Серафини. Какой полёт мысли!
no subject
Date: 2017-01-06 01:12 am (UTC)Zcash как раз пример очень сложного протокола. Я не уверен, что много людей прочитало и поняло весь протокол начиная с zkSNARKs, не говоря уж про доказательства. Ошибки в таких схемах можно годами искать.
Кстати, zero-knowledge proofs используются издавна - обычные электронные подписи это тоже zero knowledge proof в конце концов:) А вот СНАРКи да, появились недавно, теперь можно доказывать про хэш-функции тоже с zero knowledge. Но это, прямо скажем, не очень часто нужно, да и доказательство готовить - достаточно долго (если не ошибаюсь, речь идет о ключе гигабайтного размера для генерации СНАРКов).
no subject
Date: 2017-01-06 01:16 am (UTC)И да, я имел ввиду более-менее general-purpose zero-knowledge, а никакие не цифровые подписи.
Re: P=NP
Date: 2017-01-08 03:54 am (UTC)Абстракт вообще напоминает знаменитый анекдот про телеграмму в Академию Наук:
"Дорогая АН зпт я доказал теорему Ферма тчк Главная идея: в уравнении а квадрат плюс бэ квадрат равно цэ квадрат переносим цэ квадрат в левую часть тчк Подробности письмом"
Re: P=NP
Date: 2017-01-09 08:26 pm (UTC)