Роўнасць класаў P і NP
From Wikipedia, the free encyclopedia
У тэорыі алгарытмаў[ru] пытанне аб роўнасці класаў складанасці[ru] P[ru] і NP[ru] з'яўляецца адною з цэнтральных адкрытых праблем ужо больш за тры дзесяцігоддзі. Калі на яго будзе станоўчы адказ, гэта будзе азначаць, што тэарэтычна магчыма рашаць многія складаныя задачы істотна скарэй, чым цяпер.
Хуткія факты Задачы тысячагоддзя ...
Задачы тысячагоддзя |
---|
Роўнасць класаў P і NP |
Гіпотэза Ходжа |
Гіпотэза Рымана |
Квантавая тэорыя Янга — Мілса |
Існаванне і гладкасць рашэнняў ураўненняў Наўе — Стокса |
Гіпотэза Бёрча — Свінертан-Даера |
Закрыць
Праблема роўнасці класаў P і NP з'яўляецца адною з сямі задач тысячагоддзя[ru], за рашэнне якой Матэматычны інстытут Клэя (руск.) (бел. назначыў прэмію ў мільён долараў ЗША.