НП/поли

В сложности вычислений теории NP/poly — класс сложности , неоднородный аналог класса NP задач, решаемых за полиномиальное время Тьюринга недетерминированной машиной . Это недетерминированный класс сложности, соответствующий детерминированному классу P/poly .

Определение

NP/poly определяется как класс проблем, решаемых за полиномиальное время с помощью недетерминированной машины Тьюринга, имеющей доступ к полиномиально ограниченной консультативной функции.

Его эквивалентно можно определить как класс проблем, в котором для каждого размера экземпляра $n$ , существует булева схема полиномиального размера по $n$ который реализует верификатор проблемы. То есть схема вычисляет функцию $f(x,y)$ такой, что вход $x$ длины $n$ является да-экземпляром для проблемы тогда и только тогда, когда существует $y$ для чего $f(x,y)$ это правда. ^[1]

Приложения

NP/poly используется в вариации теоремы Махани о несуществовании разреженных NP-полных языков. Сама теорема Махани утверждает, что число да-экземпляров длины $n$ NP-полной задачи не может быть полиномиально ограничена, если только P = NP . Согласно варианту, количество да-экземпляров должно быть не менее $2^{n^{\epsilon }}$ для некоторых $\epsilon >0$ и для бесконечно многих $n$ , если только co-NP не является подмножеством NP/poly, что (по теореме Карпа-Липтона ) приведет к коллапсу полиномиальной иерархии . ^[2] То же предположение о вычислительной сложности , что co-NP не является подмножеством NP/poly, также подразумевает несколько других результатов по сложности, таких как оптимальность определенных методов кернеризации . ^[3]

Ссылки

^ Арора, Санджив; Барак, Боаз (2009), «Упражнение 7.7» , «Вычислительная сложность: современный подход» , Cambridge University Press, стр. 141, ISBN 9781139477369
^ Бурман, Гарри; Хичкок, Джон М. (2008), «NP-жесткие множества экспоненциально плотны, если только coNP ⊆ NP/poly», Двадцать третья ежегодная конференция IEEE по вычислительной сложности , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 1–7, doi : 10.1109/CCC.2008.21 , MR 2513482 , S2CID 2664381
^ Делл, Хольгер; ван Мелькебек, Дитер (2014), «Выполнимость не допускает нетривиальной разреженности, если только иерархия полиномиального времени не рухнет» , Журнал ACM , 61 (4): A23:1–A23:27, doi : 10.1145/2629620 , MR 3250069 , S2CID 1635025

[1] Арора, Санджив; Барак, Боаз (2009), «Упражнение 7.7» , «Вычислительная сложность: современный подход» , Cambridge University Press, стр. 141, ISBN 9781139477369

[2] Бурман, Гарри; Хичкок, Джон М. (2008), «NP-жесткие множества экспоненциально плотны, если только coNP ⊆ NP/poly», Двадцать третья ежегодная конференция IEEE по вычислительной сложности , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 1–7, doi : 10.1109/CCC.2008.21 , MR 2513482 , S2CID 2664381

[3] Делл, Хольгер; ван Мелькебек, Дитер (2014), «Выполнимость не допускает нетривиальной разреженности, если только иерархия полиномиального времени не рухнет» , Журнал ACM , 61 (4): A23:1–A23:27, doi : 10.1145/2629620 , MR 3250069 , S2CID 1635025

[1]

[2]

[3]