Что отсутствует для этого P! = доказательство NP?

Если вы покажете, что ] любой алгоритм, который решает «восстановление пароля» требует больше, чем полиномиальное время, тогда он демонстрирует, что P ≠ NP.

В противном случае, если вы только покажете, что одно конкретное решение требует больше, чем полиномиальное время, это ничего не демонстрирует. Я могу написать сортировку, требующую экспоненциального времени (перемешивать массив до тех пор, пока он не будет отсортирован), но это не значит, что нет полиномиального решения.

NP не означает «неполиномиальный», если вы так думали (и приношу свои извинения заранее, если вы не думали!). Это означает «недетерминированный многочлен». Недетерминированный алгоритм - это алгоритм, эквивалентный неограниченному количеству параллельных экземпляров алгоритма. Например, поиск правильного пароля методом грубой силы является недетерминированным полиномом: если вы представите, что проверка пароля, если ваше предположение окажется верным, занимает линейное (то есть полиномиальное) время от длины пароля, но вам необходимо проверьте произвольное количество возможных паролей (k ^ n) параллельно, тогда стоимость поиска решения с использованием этого метода будет недетерминированным полиномом.

Недетерминированный алгоритм также можно представить себе, чье состояние разветвляется на некоторых шагах. Простым примером этого является недетерминированный конечный автомат (NFA) - иногда вы не знаете, какое ребро брать между состояниями, поэтому вы берете их оба. Легко показать, что каждая NFA эквивалентна детерминированной FA, и поэтому заманчиво думать, что то же самое можно было бы доказать для других интересных классов алгоритмов. К сожалению, это трудно сделать для общего случая полиномиального алгоритма, и общее подозрение состоит в том, что они не эквивалентны, т.е. что P! = NP.

Рассуждение о том, что проблема в NP, верное: если это можно проверить за полиномиальное время, то это в NP. Даже очень простые задачи есть в NP. По сути, весь P входит в NP. (*)

Итак, вот один из способов превратить это в доказательство того, что P! = NP:

1) Показать, что «восстановление пароля» является NP-полным. То есть любую задачу в NP можно свести к «восстановлению пароля» за полиномиальное время. (т.е. существует эффективный алгоритм для преобразования любой другой проблемы NP в «восстановление пароля».)

2) Если у вас есть это, то, как упоминает Павел Швед, недостаточно, чтобы показать, что интуитивный алгоритм неполиномиален. . Вы должны показать, что не существует полиномиального алгоритма для решения «восстановления пароля». Очень сложная задача.

(*) Эдмунд тоже прав: NP означает полином на недетерминированной машине. Полиномиальная проверка - это, по сути, путь, выбранный недетерминированной машиной.

Формальная постановка этой проблемы - это та, которая принимает в качестве входных данных хешированное значение (и соль) и пытается найти пароль , который будет генерировать этот хэш: ваш базовый известная проблема обнаружения коллизий шифротекста.

В зависимости от качества хэша для этого может не требоваться экспоненциальное время. Действительно, многие широко применяемые криптографические хеш-коды выявляют атаки, которые выполняются быстрее, чем поиск в пространстве ключей.

То есть: вы (и некоторые другие респонденты) предположили , что процедура изменения пароля имеет все свойства, которые проектировщики хотели, чтобы они имели. Это должно быть доказано .

1. Как уже говорилось, «восстановление пароля» не является проблемой решения.
2. Вы не доказали, что «восстановление пароля» не имеет полиномиального алгоритма, вы просто спорили об интуитивном основания, что это не так. Тот факт, что пространство решений огромно, не означает, что нет быстрых алгоритмов для поиска решения; например, существует n! перестановок набора из n различных целых чисел, но только одно отсортировано по возрастанию, но мы можем найти его за n log n времени. Более интересный пример см. В Project Euler # 67 .
3. Даже если вы перефразировали «восстановление пароля» как проблему решения и смогли показать, что не существует алгоритма с полиномиальным временем для решения Теперь вам нужно доказать, что «восстановление пароля» является NP-полным.

Подробнее о P / NP / и т. Д. см. этот предыдущий вопрос .