Pull to refresh

Comments 23

Безумно интересно, но почти ничего не понятно =).
Но с учетом известных алгоритмов, мы ведь живем в Криптомании?
Получается так. По крайней мере пока не доказано, что P = NP или, например, что односторонние функции на самом деле таковыми не являются.
В реальной жизни я на месте официанта положил бы хоть-что на большую сумму и сказал бы, что клиентам полагается скидка или положил на чуть-меньшую и добавил новую спецзакуску «от повара» на разницу. Я думаю в хороших ресторанах еще и не такие закидоны удовлетворяют.
Очень интересно, хорошо поданы примеры, всё крайне внятно и понятно. Большое спасибо. Но только есть одна оговорка: Гаусс не гений, он — Гений!
Я занимался этим «если небольшое количество информации заранее передано между участниками, то можно установить надежный секретный код между двумя участниками сети, который позволит им общаться в закрытом порядке, используя открытые каналы связи» на военной службе. Получилось так, что до сих пор работает!
>Я занимался этим «если небольшое количество информации заранее передано между участниками, то можно установить надежный секретный код между двумя участниками сети, который позволит им общаться в закрытом порядке, используя открытые каналы связи» на военной службе. Получилось так, что до сих пор работает!
Я вам даже больше скажу, такое и сейчас много где используется.
Все выводы сделаны на основании того, что доказать возможность и найти способ — одно и то же. А это не так. Если завтра докажут, что P=NP, то это совсем не обязательно приведет к нахождению универсального способа решения всех вычислимых задач в скором времени. Например, сходимость персептрона (нейронной сети прямого распространения) доказано давно, а универсального способа построения соответствующего персептрона, аппроксимирующего заданную функцию, не найдено (насколько мне известно).
UFO landed and left these words here
Собственно об этом и речь в статье — про сложность задач «в среднем».
UFO landed and left these words here
Многие полиномиальные алгоритмы удается еще больше ускорить. Примером являются, например, алгоритмы умножения матриц, где из кубической сложности можно добиться сложности n^{2+e} для сколь угодно малого е. Понятное дело, что это можно сделать не всегда и что порядок 99,01 не намного лучше порядка 100. Однако, никто не заставляет слепо использовать полиномиальные алгоритмы. Существенным это становится только при возрастании размера задачи, особенно на фоне роста вычислительных мощностей.
> неполиномиальный симплекс метод на практике работает быстрее полиномиального метода эллипсоидов
Спорно. Зависит от области применения. Для большинства практических экземпляров задач линейного программирования — Вы правы. Но есть области, где «классический» симплекс-метод не есть приемлемый метод.
> Абсолютно согласен, на P?=NP свет клином не сошелся.
Согласен! Куда важнее вопрос NP?=coNP. Серьёзно.
Ведь это естественный математический вопрос о том, есть ли у коротких теорем короткие доказательства.
> Не будет возможности обеспечить доступ к информации нескольких людям, не делая ее таким образом доступной для всех.

Это не совсем так. Существует криптография без односторонних функций. Не будет привычных нам систем с открытым ключём, однако некоторые задачи всё-таки можно будет решать даже при условии P=NP.

Хороший пример такой задачи: представьте, что есть три человека, которые хотят пронумеровать себя числами от 1 до 3 в системе с открытыми каналами (т.е. у каждого есть канал с каждым). Так вот, даже при P=NP они могут это сделать так, что каждый будет знать только свой номер, и никакой противник не узнает какие у них номера.
Да, про Эвристику тоже пара вопросов.

> Здесь существуют сложные экземпляры задач из NP, но найти такой сложный экземпляр — сама по себе сложно решаемая задача.

Я понимаю, что всё это упрощение, но что значит найти сложный экземпляр задачи?
Сложный для конкретного алгоритма (т.е. конкретного Гаусса =))?

> В Эвристике среднее время решения задачи из NP зависит от среднего времени «обдумывания» этой задачи. Это несколько усложняет ситуацию. Допустим, в среднем, вычисление решения задачи в два раза дольше придумывания решения.

Непонятно, откуда следует тот факт, что мы не знаем распределения «плохих» входов, на которых алгоритм работает долго. Если мы знаем как они выглядят, то и искать эти входы можем достаточно быстро. Или это чему-то противоречит? Не могу сходу сообразить…

Дочитал до конца — понял, где все ответы — нужно смотреть Импальяццо и читать как конкретно определена сложность в среднем у Богданова и Тревисана =)

Собственно, ответы на мои вопросы:
1. сложный = сложный для конкретного Гаусса.
2. следуют из того, что это выполняется для любого распределения. Если мы умеем генерировать плохие ответы быстро, то мы таким образом задаём распределение, для которого это тоже верно.
1. Я бы скорее сказал, что не для конкретного Гаусса, а для конкретной задачи. Скажем, та же самая задача — найти сумму чисел от 1 до N. Для N = 100 она оказалась простой. Экземпляр этой задачи при N=100! уже не будет таким простым.
Эту задачу может быстро решать алгоритм, в который вшит ответ при N=100!.. При этом на остальных входах он может работать медленно. Именно поэтому для доказательства нижних оценок всегда требуется построить бесконечную последовательность трудных примеров.
Only those users with full accounts are able to leave comments. Log in, please.