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