Вычислительная сложность: различия между версиями

→‎Исследователи: неясен критерий включения
м (→‎Асимптотическая сложность: уточнение ссылки)
(→‎Исследователи: неясен критерий включения)
{{main|Равенство классов P и NP}}
Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. [[Математический институт Клэя]] включил эту проблему в список [[проблемы тысячелетия|проблем тысячелетия]], предложив награду размером в один миллион [[доллар США|долларов США]] за её решение.
 
== Исследователи ==
* [[Стивен Кук]]
* [[Ричард Карп]]
* [[Левин, Леонид Анатольевич|Леонид Левин]]
* [[Разборов, Александр Александрович|Александр Разборов]]
* [[Шамир, Ади|Ади Шамир]]
* [[Анатолий Плотников]]
 
== См. также ==