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

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

История

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

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

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

Ссылки

  • [1] — официальное описание проблемы (С. Кук, на английском языке).
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home