Вычислительная сложность |
4 |
Проблема равенства классов P и NP
Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.
Знаменитые учёные
•Стивен Кук
•Ричард Карп
•Леонид Левин
•Разборов, Александр Александрович
•Ади Шамир
Примечания
[1]Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4
[2]А. А. Зыков Основы теории графов. — 3-е изд. — М.: Вузовская книга, 2004. — С. 10. — 664 с. — ISBN 5-9502-0057-8
Ссылки
•Курсы по теории вычислимости и сложности вычислений (http://www.csin.ru/courses#computability)
•Юрий Лифшиц « Современные задачи теоретической информатики (http://yury.name/modern.html)». Курс лекций по алгоритмам для NP-трудных задач.
•А. А. Разборов Theoretical Computer Science: взгляд математика (http://offline.computerra.ru/print/offline/ 2001/379/6782/) // Компьютерра. — 2001. — № 2. ( альтернативная ссылка (http://www.mi.ras.ru/ ~razborov/computerra.ps))
•А. А. Разборов О сложности вычислений (http://www.mccme.ru/free-books/matpros/i4127141.pdf.zip) //
Математическое просвещение. — МЦНМО, 1999. — № 3. — С. 127-141.