Аннотация: Здесь я размышляю над одной из проблем тысячелетия.
Я не математик и весьма далек от специфических терминов. Но у меня есть некоторые идеи, что могут помочь взглянуть на проблему под другим углом.
По моему мнению, неверно само понимание деления математических задач на два класса. P и NP. Чтобы более полно взглянуть на проблему, давайте введем два понятия. D - решение и A - алгоритм. Каждая математическая задача имеет два аспекта. Первый это - количество решений, которые удовлетворяют условиям задачи, второй - количество путей или алгоритмов, с помощью которых задачу можно решить.
Таким образом, все задачи можно разделить на четыре класса.
1. Задачи, в которых одно решение можно получить одним способом. Собственно говоря, это все задачи класса P.
D*A*P=1*1*P=P
Пример такой задачи: Сколько метров пробежал атлет?
2. Задачи, в которых решение складывается из множества алгоритмов. К таким задачам относятся: задача коммивояжера, решение пятнашек, проблема Штейнера и другие.
D*A*P=1*A*P=AP
Пример AP задачи: какой из десяти бегунов пробежал быстрее всех? Проблема заключается в том, что задача эта лежит не в области абсолютного решения, а в области относительного решения. Никто не может сказать, что данная девушка на самом деле самая красивая в мире не сравнив ее с другими девушками. При чем, вывод тем больше точен, с чем большим количеством девушек удалось сравнить красавицу. То есть, чтобы получить абсолютно правильное решение, нужно сравнить ВСЕХ бегунов друг с другом. Иначе говоря, задача AP решается только полным перебором. И проверяется также полным перебором.
3. Задачи, в которых один алгоритм позволяет получать множество решений. К таким задачам относятся: некоторые задачи о независимом множестве, Гамильтонов граф, криптографическое шифрование с открытым ключом и другие.
D*A*P= D *1*P= DP
Пример DP задачи: какая дорога ведет из города А в город В, при условии, что место нахождения города В неизвестно. Решение такой проблемы также лежит в области логики больше, чем в области математики. Проблема заключается в том, что найти нужное решение легко, сложно понять какое решение нужное. То есть решить такую задачу очень сложно, но проверить ее легко. Достаточно просто пройти из города А в город В. Чтобы найти город В нужно ходить из города в город, пока наконец он не будет найден. Далее просто прокладывается кратчайшая дорога и все. То есть решается задача долго. Верное решение можно найти только перебором. А проверить решение можно очень легко - просто проверить соответствие полученного решения данному алгоритму.
4. Задачи, в которых множество алгоритмов позволяет получать множество решений.
D*A*P= DAP
Делятся такие задачи на две категории.
Первая категория, где D = A, то есть для каждого алгоритма существует свое собственное решение. К таким задачам относятся: задачи о выполнимости булевых формул, банковское шифрование данных и другие.
Например, кто из бегунов быстрее всего добежал из города А каждый в свой город, при условии, что нам неизвестно место нахождения ни одного города.
Проблема заключается в двух моментах. Не знаешь, где искать и не знаешь, как искать.
Вторая категория, где D не равно A, то есть для неопределенного количества алгоритмов существует неизвестное число решений. К таким задачам относится проблема расшифровки генетического кода.
Например, кто из бегунов прибежал быстрее всего в неизвестное количество городов, при условии, что местонахождения городов неизвестно.
Здесь три проблемы. Не знаешь: как искать, где искать и что искать.
Проверка решения обеих этих категорий занимает столько же времени, что нахождение решений. Чтобы проверить работу генетика, нужно самому быть генетиком.
Это мое предположение! Я нисколько не заявляю, что так есть на самом деле. Но из этого предположения есть важное следствие:
Все три класса AP, DP, DAP относятся к классу NP, но решаются по разному. То есть, невозможно найти одинаковое решение для этих задач, чтобы доказать равенство или неравенство P и NP.
Мое мнение, что математикам будет проще разбираться в этом вопросе, если они примут за аксиому существование четырех классов задач, а не двух.
Большая путаница.
Из-за того, что решение NP задач лежит больше в области логики, чем математики, и очень сильно зависит от человеческого фактора, возникает большая путаница. Например, криптографическое шифрование. Почему, чтобы взломать чужой кошелек, одному компьютеру нужны миллиарды лет, а другой компьютер проверяет правильность ключа за доли секунды? Фишка в том, что для одного компьютера задача лежит в области DP задач и решается исключительно перебором, а для другого задача лежит в области P задач и проверяется соответствием решения и алгоритма. Или другой пример, чтобы доказать, что один из восьми тысяч опытов Томаса Эдисона оказался успешным, нужно просто зажечь вольфрамовую электрическую лампочку. Это задача P класса. Чтобы доказать, что это единственный успешный вариант электрической лампочки, нужно повторить все восемь тысяч опытов. Это задача из AP-класса.
Таким образом, из всего выше сказанного можно сделать вывод, что сложность поиска решения зависит не от характера задачи и исходных данных, а от заданного вопроса и желаемого результата. Понимание равенства или неравенства P против NP ничего не дает человеку, который не умеет правильно поставить перед собой задачу и грамотно наметить пути ее возможного решения.