Подсчет иерархии
В теории сложности иерархия подсчета представляет собой иерархию классов сложности . Это аналог полиномиальной иерархии , но с NP заменой на PP . Он был определен в 1986 году Клаусом Вагнером. [ 1 ] [ 2 ]
Точнее, нулевой уровень — это C 0 P = P , а ( n +1)-й уровень — C n +1 P = PP. С н П (т.е. PP с оракулом C n ). [ 2 ] Таким образом:
- С 0 П = П
- С 1 П = ПП
- С 2 П = ПП ПП
- С 3 П = ПП ПП ПП
- ...
Иерархия подсчета содержится в PSPACE . [ 2 ] По теореме Тоды полиномиальная иерархия PH целиком содержится в P ПП , [ 3 ] и поэтому в C 2 P = PP ПП .
Ссылки
[ редактировать ]- ^ Вагнер, Клаус В. (1986). «Сложность комбинаторных задач с кратким входным представлением». Акта Информатика . 23 : 325–356. дои : 10.1007/BF00289117 .
- ^ Перейти обратно: а б с «Зоопарк сложности» . Проверено 26 июня 2024 г.
- ^ Тода, Сейносукэ (октябрь 1991 г.). «PP так же сложен, как иерархия с полиномиальным временем» . SIAM Journal по вычислительной технике . 20 (5): 865–877. CiteSeerX 10.1.1.121.1246 . дои : 10.1137/0220053 . ISSN 0097-5397 .
Дальнейшее чтение
[ редактировать ]- Торан, Хакобо (1991). «Классы сложности, определяемые путем подсчета кванторов». Журнал АКМ . 38 (3): 753–774. дои : 10.1145/116825.116858 . МР 1125929 .
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |