Является ли

В «последнем абзаце» «первой страницы» следующего документа:

Викраман Арвинд , Йоханнес Коблер , Уве Шенинг , Райнер Шулер , "Если у NP есть схемы полиномиального размера, то MA = AM", Теоретическая информатика, 1995.

Я столкнулся с несколько нелогичным утверждением:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

Я думаю, что идентичность выше выводится из следующего:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

и

$(\Pi^P_2)^{NP} = \Pi^P_3$

Первый проще записать как , что довольно странно!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Изменить: В свете комментария Кристоффера ниже, я хотел бы добавить следующее вдохновляющее замечание из книги сложности Гольдрайха (стр. 118-119):

Должно быть понятно, что класс может быть определен для двух классов сложности и , при условии, что связан с классом стандартных машин, который естественным образом обобщается на класс машин оракула. На самом деле класс определяется не на основе класса а по аналогии с ним. В частности, предположим, что$C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$это класс множеств, которые распознаются (или скорее принимаются) машинами определенного типа (например, детерминистическими или недетерминированными) с определенными ограничениями ресурса (например, ограничениями времени и / или пространства). Затем мы рассмотрим аналогичные машины оракула (т.е. того же типа и с теми же границами ресурса) и скажем, что если существует адекватная машина оракула (то есть этого типа и границ ресурса ) и множество таким образом, что принимает множество .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

- это набор языков, определяемый чередующейся машиной Тьюринга в экзистенциальном, а затем универсальном состоянии с оракулом в NP. Как универсальная, так и экзистенциальная части могут запрашивать NP.${\Sigma_2^P}^{NP}$

Следовательно, в этом случае вы решили записать это как тогда вы должны думать об этом как ( N P N P A ∪ A ) (под ∪ я имею в виду оракула либо A, либо Н П А ).$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Следовательно, равно ( N P ( N P N P ) ) N P, что, безусловно, равно ( N P N P N P ), поскольку каждый запрос, который вы можете сделать к оракулу N P , вы можете сделать это к п п н п оракул.${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$

$i\geq 2$$\sum_i^p=NP^{\sum_{i-1}SAT}$$\sum_{i}SAT$$i$$\sum_i^p$$\sum_2^p=NP^{SAT}$$\sum_2^p=NP^{NP}$$i=3$$NP^{NP^{NP}}$$\sum_{2}SAT$