Равенство классов P и NP

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Классы P и NP 2 Содержание проблемы 3 История 4 Ссылки

[править] Классы P и NP

В конечном счете проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли что ответ на этот вопрос можно быстро найти(за полиномиальное время и используя полиномиальную память)? Рассмотрим, например, задачу о суммах подмножеств, пример задачи, решение которой легко проверить, но кажется(но не доказано) сложно решить. Пусть дан набор чисел. Верно ли, что сумма непустого подмножества этих чисел равна 0? Например, верно ли что среди чисел {−2, −3, 15, 14, 7, −10} есть такие, что их сумма равна 0? Ответ ДА, однако надо немного подумать, прежде чем это понять. А если набор чисел будет больше, то потребуется еще больше времени на решение. С другой стороны, если сказать "Ответ ДА, потому что −2 −3 + 15 −10 = 0 ", то это утверждение легко проверяется несколькими сложениями. Проверка того, что сумма равна нулю гораздо проще, чем поиск соответствующих слагаемых в исходной постановке задачи. Информация, необходимая для проверки положительного ответа называется сертификат. Итак, мы пришли к выводу, что если есть подходящий сертификат, то можно легко(за полиномиальное время) проверить положительный ответ, поэтому наша задача принадлежит классу NP.

Ответ на вопрос о равенстве классов P и NP определил бы, действительно ли подобные задачи легче проверить, чем решить(если P=NP), или решить их столь же просто , что и проверить(в противном случае). Это применимо ко всем подобным задачам, а не только к задаче о суммах подмножеств. Так же это применимо к задачам, ответ на которые сложнее, чем ДА или НЕТ.

[править] Содержание проблемы

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

[править] История

Из определения классов P и NP сразу вытекает следствие: . Однако до сих пор ничего не известно о строгости этого включения, т. е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные NP-задачи (так назвыаемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.

Впервые вопрос о равенстве классов был поставлен независимо Куком и Левиным в 1971 г. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 г. среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что вопрос не зависит от текущей системы аксиом и, таким образом, не может быть доказан или опровергнут.

В настоящий момент проблема равенства классов P и NP является одной из семи проблем, за решение которых Математический институт Клэя назначил премию в 1 млн. долларов США.

[править] Ссылки

• [1] — официальное описание проблемы (С. Кук, на английском языке).