Теорема Махани
Теорема Махани — это теорема в теории вычислительной сложности, доказанная Стивеном Махани, которая утверждает, что если любой разреженный язык является NP-полным , то P = NP. Кроме того, если любой разреженный язык является NP-полным относительно редукций Тьюринга , то иерархия полиномиального времени схлопывается до . [1]
Аргумент Махани на самом деле не требует, чтобы разреженный язык был в NP, поэтому существует разреженное NP-трудное множество тогда и только тогда, когда P = NP. Это происходит потому, что существование NP-трудного разреженного множества подразумевает существование NP-полного разреженного множества. [2]
Ссылки
- ^ Махани, Стивен Р. (октябрь 1982 г.). «Разреженные полные множества для NP: решение гипотезы Бермана и Хартманиса». Журнал компьютерных и системных наук . 25 (2): 130–143. doi :10.1016/0022-0000(82)90002-2. hdl : 1813/6257 .
- ^ Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1990). Структурная сложность II . Спрингер . стр. 130–131. ISBN 3-540-52079-1.
 | Эта статья по информатике — заглушка . Вы можете помочь Википедии, расширив ее. |
