Низкая и высокая иерархия
(Перенаправлено с низкой иерархии )
В теории сложности вычислений низкая иерархия и высокая иерархия уровней сложности были введены в 1983 году Уве Шёнингом для описания внутренней структуры класса сложности NP . [1] Низкая иерархия начинается с класса сложности P и растет «вверх», а высокая иерархия начинается с класса сложности NP и растет «вниз». [2]
Позже эти иерархии были распространены на множества за пределами NP.
Структура иерархий высокого/низкого уровня имеет смысл только в предположении, что P не является NP . С другой стороны, если нижняя иерархия состоит хотя бы из двух уровней, то P не является NP. [3]
Неизвестно, охватывают ли эти иерархии все NP.
Ссылки
[ редактировать ]- ^ Уве Шенинг (1983). «Низкая и высшая иерархия внутри NP». Дж. Компьютер. Сист. Наука . 27 (1): 14–28. дои : 10.1016/0022-0000(83)90027-2 .
- ^ «Теория сложности и криптология», Йорг Роте с. 232
- ^ Лейн А. Хемаспаандра, «Низкость: критерий для NP-P», ACM SIGACT News , 1993, том. 24, №2, стр. 11-14. дои : 10.1145/156063.156064