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

Question

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

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

Answer 1

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

На самом деле, "восстановление пароля" не является описанием стандартной вычислительной проблемы. Кажется, что формально алгоритмы взлома паролей используют своего рода "оракула", который может ответить, является ли данная строка правильным паролем. Однако 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) Если у вас есть это, то, как упоминает Павел Швед, недостаточно показать, что интуитивный алгоритм является неполиномиальным. Вы должны показать, что не существует полиномиального алгоритма для решения "восстановления пароля". Очень сложное задание.

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Вы доказали, что P =/= NP в присутствии "Oracle" (это то, что говорит, правильный пароль или нет).

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

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

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

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