WikiDer > Теорема Махейна - Википедия
Mahaneys theorem - Wikipedia
Теорема Махани это теорема в теория сложности вычислений доказано Стивеном Махани, который утверждает, что если скудный язык является NP-Complete, то P = NP. Кроме того, если есть Редукция Тьюринга от NP-полного разреженного языка до P, то полиномиальная иерархия рушится до ∆_2 (НП ^ {НП [вход]}).[1]
Рекомендации
- ^ Махани, Стивен Р. (октябрь 1982 г.). «Редкие комплекты для NP: решение гипотезы Бермана и Хартманиса». Журнал компьютерных и системных наук. 25 (2): 130–143. Дои:10.1016/0022-0000(82)90002-2. HDL:1813/6257.
 | Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это. |