Эн Ка : другие произведения.

Размышления о проблеме p=np?

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  • Аннотация:
    Здесь я размышляю над одной из проблем тысячелетия.


   Я не математик и весьма далек от специфических терминов. Но у меня есть некоторые идеи, что могут помочь взглянуть на проблему под другим углом.
   По моему мнению, неверно само понимание деления математических задач на два класса. 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 ничего не дает человеку, который не умеет правильно поставить перед собой задачу и грамотно наметить пути ее возможного решения.

 Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"