Question

Равны ли классы сложности P и NP?

Answer 1

Проблема равенства классов P и NP является одной из семи задач 1000 летия, за решение который математический институт Клэя назначили премию в 1.000.000 $

Answer 2

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