PH (сложность)
В теории сложности вычислений класс сложности PH представляет собой объединение всех классов сложности в полиномиальной иерархии :
PH был впервые определен Ларри Стокмейером . [1] Это частный случай иерархии ограниченной знакопеременной машины Тьюринга . Он содержится в П. #П = П ПП и PSPACE .
PH имеет простую логическую характеристику : это набор языков, выражаемых логикой второго порядка .
Отношения с другими классами [ править ]
PH содержит почти все известные классы сложности внутри PSPACE ; в частности, он содержит P , NP и co-NP . Он даже содержит вероятностные классы, такие как BPP. [2] (это теорема Сипсера–Лаутмана ) и RP . Однако есть некоторые свидетельства того, что BQP , класс задач, решаемых за полиномиальное время квантовым компьютером , не содержится в PH . [3] [4]
P = NP тогда и только тогда, когда P = PH . [5] Это может упростить потенциальное доказательство P ≠ NP , поскольку необходимо только отделить P от более общего класса PH .
PH является подмножеством P #П = П ПП по теореме Тоды ; класс задач, решаемых с помощью машины Тьюринга с полиномиальным временем с доступом к #P или, что эквивалентно, PP оракулу ), а также в PSPACE .
Примеры [ править ]
![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел пуст. Вы можете помочь, добавив к нему . ( февраль 2023 г. ) |
Ссылки [ править ]
- ^ Стокмейер, Ларри Дж. (1977). «Иерархия полиномиального времени» . Теор. Вычислить. наук. 3 : 1–22. дои : 10.1016/0304-3975(76)90061-X . Збл 0353.02024 .
- ^ Лаутеманн, Клеменс (8 ноября 1983 г.). «БПП и полиномиальная иерархия» . Письма об обработке информации . 17 (4): 215–217. дои : 10.1016/0020-0190(83)90044-3 . ISSN 0020-0190 .
- ^ Ааронсон, Скотт (2009). «BQP и полиномиальная иерархия». Учеб. 42-й симпозиум по теории вычислений (STOC 2009) . Ассоциация вычислительной техники . стр. 141–150. arXiv : 0910.4698 . дои : 10.1145/1806689.1806711 . ЕССС ТР09-104 .
- ^ «Наконец-то проблема, которую когда-либо смогут решить только квантовые компьютеры» . 21 июня 2018 г.
- ^ Хемаспаандра, Лейн (2018). «17.5 Классы сложности». В Розене, Кеннет Х. (ред.). Справочник по дискретной и комбинаторной математике . Дискретная математика и ее приложения (2-е изд.). ЦРК Пресс. стр. 1308–1314. ISBN 9781351644051 .
Общие ссылки [ править ]
- Бюргиссер, Питер (2000). Полнота и редукция в теории алгебраической сложности . Алгоритмы и вычисления в математике. Том. 7. Берлин: Шпрингер-Верлаг . п. 66. ИСБН 3-540-66752-0 . Збл 0948.68082 .
- Зоопарк сложности : PH