У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP[1] до обчислень з оракулом.
Існує багато еквівалентних визначень класів поліноміальної ієрархії. Наведемо одне з них.
Для визначення оракула в поліноміальній ієрархії визначимо
де P — це множина задач, розв'язних за поліноміальний час. Тоді для i ≥ 0 визначимо
де AB — множина задач вибору, що вирішуються за поліноміальний час машиною Тьюринга, розширеною за допомогою оракула для якоїсь задачі з класу B. Наприклад, , і — це клас задач, що розв'язуються за поліноміальний час з оракулом для будь-якої задачі з NP.[2]
Відношення між класами в поліноміальній ієрархії
[ред. | ред. код]
Визначення припускають такі відношення:
На відміну від арифметичних і аналітичних ієрархій, всі включення в яких строгі, в поліноміальній ієрархії питання про строгість все ще відкрите.
Якщо якийсь , або якийсь , то ієрархія стискається до рівня 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 є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
- Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
- Докладні рекомендації: див. Вікіпедія:Переклад.
|