У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP[1] до обчислень з оракулом.
Існує багато еквівалентних визначень класів поліноміальної ієрархії. Наведемо одне з них.
Для визначення оракула в поліноміальній ієрархії визначимо
![{\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85e95bf698cd9d13b3af34d5a445e6e0cc7c8a7b)
де P — це множина задач, розв'язних за поліноміальний час. Тоді для i ≥ 0 визначимо
![{\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fb5da7ef9ad3e071ceddfb9e5f2e06eb8a58c99)
![{\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f31a927c534423d0b98ea6352602c9605873c0ca)
![{\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18d21265d51e043df1876bde23704717a8fb9989)
де AB — множина задач вибору, що вирішуються за поліноміальний час машиною Тьюринга, розширеною за допомогою оракула для якоїсь задачі з класу B. Наприклад,
, і
— це клас задач, що розв'язуються за поліноміальний час з оракулом для будь-якої задачі з NP.[2]
Відношення між класами в поліноміальній ієрархії
[ред. | ред. код]
Визначення припускають такі відношення:
![{\displaystyle \Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d376e957e06779a22da65d8a0180609da6bf0aca)
![{\displaystyle \Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de430a32e7b85008c691703305a06888d84a4e9d)
![{\displaystyle \Sigma _{i}^{\rm {P}}={\rm {co}}\Pi _{i}^{\rm {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04359fb9a2a1c737e7d9fcf748352bb7eb5c1e80)
На відміну від арифметичних і аналітичних ієрархій, всі включення в яких строгі, в поліноміальній ієрархії питання про строгість все ще відкрите.
Якщо якийсь
, або якийсь
, то ієрархія стискається до рівня k: для всіх
,
.[3] На практиці це означає, що рівність класів P і NP повністю руйнує поліноміальних ієрархію.
Об'єднання всіх класів поліноміальної ієрархії є класом PH.
Поліноміальна ієрархія є аналогом (меншої складності) для експоненційної ієрархії[en] та арифметичної ієрархії[en].
Відомо, що PH міститься в PSPACE, але не відомо чи рівні ці два класи.
Кожен клас у поліноміальній ієрархії містить
-повні задачі (задачі повні відносно зведення за Карпом за поліноміальний час).
- ↑ Arora and Barak, 2009, pp.97
- ↑ Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans
- ↑ Arora and Barak, 2009, Theorem 5.4
| В іншому мовному розділі є повніша стаття Polynomial hierarchy(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
- Дивитись автоперекладену версію статті з мови «англійська».
- Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
- Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
- Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
- Докладні рекомендації: див. Вікіпедія:Переклад.
|