?

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