Введение

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

Ключевые слова

равенство классов P и NP, полиноминальное время

Формулировка задачи

Проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли проверить решение задачи столь же ресурсозатратно, как и отыскать решение [1]?

История проблемы

Вопросы о вычислительной сложности задач поднимаются многими учеными и математиками начиная с 1956 года, когда появились и начали использоваться для вычисления первые компьютеры.

Впервые вопрос о равенстве этих классов были поставлены Стивеном Куком и Леонидом Левиным в 1971 и 1973 годах.

В настоящий момент решение задачи отсутствует и хотя большинство математиков считают, что эти классы не равны, однако доказательства этому до сих пор нет [1].

Мой взгляд на решение данной задачи

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

Формулы и их объяснение:

1. Формула P = x + y + z = P

o x — количество чисел в задаче (например, 4 числа).

o y — количество сравнений, которые необходимо выполнить. Например, для последовательности 1 + 2 требуется 1 сравнение, а для 1 + 2 + 3 — уже 2 сравнения.

o z — количество сравнений, которые нужно выполнить в последний раз (например, 3 сравнения).

2. Формула PN = y + z = PN

o y — количество сравнений, как и в формуле P.

o z — количество сравнений в последний раз, как и в формуле P.

Подробное объяснение формул

Формула P

Предположим, у нас есть задача с 4 числами. Для её решения необходимо выполнить 10 сравнений (в примере ниже это 5 чисел). Если считать, что у среднего человека на сравнение двух чисел уходит 1 секунда, то для составления этого примера потребуется 10 секунд. Однако, чтобы убедиться, что пример верный, необходимо провести дополнительную проверку: в последний раз сравниваем все числа. Это добавляет ещё 4 секунды. Таким образом, общее время решения задачи составляет 14 секунд.

Формула PN

В этом случае процесс упрощается. Нам уже не нужно составлять пример с нуля. Достаточно только сравнить числа в последний раз и проверить результат. Это занимает 8 секунд.

Вопрос о существовании задачи, лежащей в P, но не в PN

Возникает вопрос: существует ли задача, которая принадлежит классу P, но не принадлежит классу PN?

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

Разница лишь в том, что в классе P требуется чуть больше действий. Однако, поскольку данные одинаковы, это равносильно решению и проверке разных примеров с одинаковыми исходными данными.

Такая задача была бы странной, так как в ней либо присутствовали бы лишние данные, либо их бы не хватало. Именно поэтому такой задачи не существует.

Решение по моему способу

Рассмотрим конкретный пример на примере простой задачи на сложение последовательности простых чисел:

Пример: -2 - 6 + 5 + 2 + 1 = 0

· x = 5 (количество чисел).

· y = 10 (количество сравнений).

· z = 4 (количество сравнений в последний раз, для проверки результата).

Применяя формулу P:

x + y + z = 5 + 10 + 4 = 19 секунд — время, необходимое для решения задачи.

Применяя формулу PN:

y + z = 10 + 4 = 14 секунд — время, необходимое для проверки решения.

Разница во времени:

19 - 14 = 5 секунд.

Ответ: В данном случае время решения занимает на 5 секунд больше, чем время проверки примера.

Заключение

На основании приведённых рассуждений и примеров я прихожу к выводу, что предложенная теория неверна. Классы P и NP не могут быть равны, поскольку не равны последовательности и количество шагов для вычисления и для проверки правильности вычисленного решения.

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

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