?

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 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)