Низкая и высокая иерархия

В теории сложности вычислений низкая иерархия и высокая иерархия уровней сложности были введены в 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

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

[1] Уве Шенинг (1983). «Низкая и высшая иерархия внутри NP». Дж. Компьютер. Сист. Наука . 27 (1): 14–28. дои : 10.1016/0022-0000(83)90027-2 .

[2] «Теория сложности и криптология», Йорг Роте с. 232

[3] Лейн А. Хемаспаандра, «Низкость: критерий для NP-P», ACM SIGACT News , 1993, том. 24, №2, стр. 11-14. дои : 10.1145/156063.156064

[ 1 ]

[ 2 ]

[ 3 ]