Классы сложности, где

Одной из возможных причин изучения классов сложности вычислений является понимание возможностей различных видов вычислительных ресурсов (случайность, недетерминизм, квантовые эффекты и т. Д.). Если мы посмотрим на это с этой точки зрения, то кажется, что мы можем получить одну правдоподобную аксиому для любой попытки определить, какие вычисления осуществимы в некоторой модели:

• Любое возможное вычисление всегда может вызвать другое возможное вычисление в качестве подпрограммы. Другими словами, предположим, что программы считаются выполнимыми. Затем, если мы создадим новую программу, подключив P и Q , так что P делает вызовы подпрограммы для Q , тогда эта новая программа также выполнима.$P,Q$$P$$Q$$P$$Q$

В переводе на язык классов сложности эта аксиома соответствует следующему требованию:

• Если является классом сложности предназначен для захвата , который вычисление выполнимо в некоторой модели, то мы должны иметь C C = C .$C$$C^C = C$

(Здесь представляет вычисления в C , который может вызвать оракул из C ;. Это класс сложности оракул) Итак, давайте называть класс сложности C правдоподобным , если она удовлетворяет C C = C .$C^C$$C$$C$$C$ $C^C=C$

Мой вопрос: о каких классах сложности мы знаем, которые правдоподобны (по этому определению правдоподобно)?

Так , например, правдоподобно, так как P P = P . Есть ли у нас Б П П Б П П = Б П П ? А как насчет B Q P B Q P = B Q P ? Какие еще классы сложности соответствуют этому критерию?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Я подозреваю, что (или, по крайней мере, это было бы нашим лучшим предположением, даже если мы не можем доказать это). Существует ли класс сложности, который фиксирует недетерминированные вычисления и который является правдоподобным согласно этому определению? Если мы позволим C обозначать наименьший класс сложности, такой, что N P ⊆ C и C C ⊆ C , есть ли какая-либо чистая характеристика этого C ?$NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

было доказано всильных и слабых сторонах квантовых вычисленийBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

По сложности зоопарка, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Вот некоторые ответы на некоторые из вопросов, но, конечно, не все из них:

Видимо, согласно Википедии , мы имеем , B P P B P P = B P P , P S P A C E P S P A C E = P S P $P^P=P$$BPP^{BPP}=BPP$ , L L = L , и ⊕ P ⊕ P = ⊕ P . Смотрите такжеЧто такое класс сложности ⊕ P$PSPACE^{PSPACE}=PSPACE$$L^L=L$$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$ , который отмечаетчто.$\oplus P^{\oplus P} = \oplus P$

Также, если , то C замкнуто относительно дополнения. Таким образом, маловероятно, что N P N P = N P : это будет означать, что N P = co- N P , что кажется маловероятным. Похоже, наименьший вероятный класс сложности, который содержит N P является P H (см. Википедия ).$C^C=C$$C$$NP^{NP}=NP$$NP=\textit{co-}NP$$NP$$PH$

Я не знаю , какова ситуация с . Я не знаю, есть ли другие интересные примеры вероятных классов сложности.$BQP$

Класс сложности называется само-низко точно , когда C C = C . Вообще, «бесцеремонность» много изучалась в 80-х и 90-х годах - Google многое раскроет для вас.$C$$C^C = C$

Этот комментарий перечисляет L (logspace), NC (глубина полилога), P, BPP, BQP и PSPACE в качестве примеров классов с собственной низкой сложностью.