Чего не хватает для этого P! = NP PROUCE?

Question

Я попытался восстановить пароль. Подумав об этом, я признал, что проблема «восстановление пароля» является очень хорошим примером проблемы NP. Если вы знаете пароль, очень легко проверить его в полиномиальное время. Но если вы не знаете пароль, вы должны искать все пространство возможных решений, которые можно показать, чтобы занять экспоненциальное время.

Теперь мой вопрос: разве это не демонстрирует, что P! = NP, поскольку «восстановление пароля» является элементом NP, который может быть показан, чтобы потребовать больше, чем полиномиальное время для запуска?

Answer 1

Проблема не показывает, что восстановление пароля не полиномиально, поскольку ясно, что это так-вы должны искать экспоненциальное пространство ответов.

На самом деле, «переоборудование пароля» на самом деле не описание стандарта вычислительная проблема. Анкет Похоже, что формально алгоритмы ловушки пароля принимают какой -то «Oracle», который может ответить, является ли данная строка правильным паролем. Однако P и NP определяются с точки зрения машин Тьюринга, которые принимают строки в качестве входных данных.

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Answer 5

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

Для получения подробной информации о P/NP/и т. Д. посмотри это Предыдущий вопрос.

Answer 6

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

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

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

Answer 7

Написал этот ответ, потому что у меня была эта идея в какой -то момент, и ответы здесь были не удовлетворительными.

Вы доказали, что p =/= np при наличии «оракула» (это то, что говорит, правильным ли пароль или нет).

Было показано, что вы на самом деле не можете доказать оригинальный P против NP, используя оракулы (этот метод называется релятивизацией).

Чтобы доказать первоначальную проблему, вы должны определить Oracle с точки зрения машины Тьюринга. Другими словами, вы должны описать, что подтверждает пароль с входом, а затем доказать, что нет алгоритма, который может угадать пароль, учитывая код проверки пароля.

Обратите внимание, что вы должны сделать это для любого возможного быстрого проверки пароля. Единственным требованием алгоритма проверки пароля является то, что он работает в полиномиальное время в отношении длины пароля.

Таким образом, учитывая какой -либо возможный алгоритм, который проверяет, правильный ли пароль или нет в полиномиальное время, вы должны написать алгоритм, который считывает алгоритм проверки и пытается угадать, что пароль находится в полиномиальном времени. Если вы можете доказать или опровергнуть, что такой алгоритм существует, вы решили проблему.