Помогите разобраться с P vs NP

[Bakaringo]

Не совсем уверен, что в правильном подфоруме завожу тему, и поиском тоже не пользовался как следует, так что заранее извините.

Помогите разобраться с вопросом о равенстве/не равенстве классов.
Рассмотрим такую задачу СЕЙФ:
Пусть у нас есть сейф и на нем висит кодовый замок, у которого есть n колесиков с цифрами от 0 до 9.
Вопрос: существует ли строка из n цифр, открывающая замок? (т.е. может быть, кодовый замок висит просто так, и не открывает сейф)

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

Алгоритмов решения этой задачи кроме полного перебора нет, потому что у нас вообще больше никакой информации о сейфе нет. Поскольку это задача из NP, она сводится к задачам из NPC, и поскольку у нее нет полиномиального алгоритма решения значит и у NPC их нет (иначе было бы противоречие). И получается что P!=NP.

Очевидно, что это слишком простое рассуждение, и где-то что-то должно быть не так, иначе все бы давно уже доказали. В голову приходит только то, что задача СЕЙФ не очень математическая...

[Xaositect]

Bakaringo в сообщении #915800 писал(а):

В голову приходит только то, что задача СЕЙФ не очень математическая...

Да, это проблема. Классы P и NP определяются формально, и нужно математическое решение.

Bakaringo в сообщении #915800 писал(а):

Алгоритмов решения этой задачи кроме полного перебора нет, потому что у нас вообще больше никакой информации о сейфе нет.

Может быть, можно простучать сейф звуковыми волнами, составить схему механизма и узнать код замка.
Собственно, проблема P vs NP и состоит в том, чтобы доказать, что в строгой математической постановке не может быть каких-то вот таких хитрых обходных путей.

[Toucan]

JonLee, предупреждение за спам. Сообщение удалено.

[ArshakA]

Bakaringo, дело в том, что вы в своем подборе используете оракул — сейф — который мгновенно проверяет правильность ответа. Поэтому вы доказали, что задача принадлежит классу $NP^{A}$, а не $NP$. Без сейфа вычислить правильность пароля у вас никак не получится, ни машина тьюринга, ни более мощные вычислители в принципе не умеют угадывать загаданные кем-то числа. Не хватает данных.

Тот факт, что существует оракулы для которых $NP^{A} \not= P^{A}$ известен : теорема Бейкера — Гилла — Соловэя.