Поліноміальна ієрархія

У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP[1] до обчислень з оракулом.

Визначення

Існує багато еквівалентних визначень класів поліноміальної ієрархії. Наведемо одне з них.

Для визначення оракула в поліноміальній ієрархії визначимо

де P — це множина задач, розв'язних за поліноміальний час. Тоді для i ≥ 0 визначимо

де AB — множина задач вибору, що вирішуються за поліноміальний час машиною Тьюринга, розширеною за допомогою оракула для якоїсь задачі з класу B. Наприклад, , і  — це клас задач, що розв'язуються за поліноміальний час з оракулом для будь-якої задачі з NP.[2]

Відношення між класами в поліноміальній ієрархії

Визначення припускають такі відношення:

На відміну від арифметичних і аналітичних ієрархій, всі включення в яких строгі, в поліноміальній ієрархії питання про строгість все ще відкрите.

Якщо якийсь , або якийсь , то ієрархія стискається до рівня k: для всіх , .[3] На практиці це означає, що рівність класів P і NP повністю руйнує поліноміальних ієрархію.

Об'єднання всіх класів поліноміальної ієрархії є класом PH.

Поліноміальна ієрархія є аналогом (меншої складності) для експоненційної ієрархії та арифметичної ієрархії.

Нерозв'язана проблема інформатики:
(більше нерозв'язаних проблем інформатики)

Відомо, що PH міститься в PSPACE, але не відомо чи рівні ці два класи.

Кожен клас у поліноміальній ієрархії містить -повні задачі (задачі повні відносно зведення за Карпом за поліноміальний час).

Примітки

  1. Arora and Barak, 2009, pp.97
  2. Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans
  3. Arora and Barak, 2009, Theorem 5.4
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.