Dobra referencja dla operatorów klasy złożoności?

Interesuje mnie, czy istnieją jakieś dobre artykuły ekspozycyjne lub ankiety, do których mogę się odnieść, pisząc o operatorach klas złożoności : operatorach, które przekształcają klasy złożoności, np. Dodając do nich kwantyfikatory.

Przykłady operatorów

Poniższe można interpretować jako absolutną minimalną listę operatorów, którą odpowiedź powinna umieć opisać. Tutaj jest dowolnym zestawem języków, nad dowolnym skończonym alfabetem .$\mathbf C$$\Sigma$

$\exists \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\\quad \bigl[x \in L \iff \exists c \in \Sigma^{f(|x|)}: (x,c) \in A \bigr] \end{array} \right\}\right.$

• Operator najwyraźniej został wprowadzony przez Wagnera [1], aczkolwiek z notacją zamiast . Najbardziej znanym przykładem klasy skonstruowanej w ten sposób . Ten operator jest wyposażony w uzupełniający kwantyfikator , w którym definicji jest zastąpione przez , co pozwala łatwo zdefiniować całą hierarchię wielomianową: na przykład . Może to być pierwszy zdefiniowany operator.$\exists$$\bigvee\! \mathbf C$$\exists \mathbf C$$\mathsf{NP} = \exists \mathsf P$$\forall$$\exists c$$\forall c$$\mathsf{\Sigma_2^P P = \exists \forall P}$

$\oplus \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n)) \;\forall x \in \Sigma^\ast: \\ \quad\bigl[x \in L \iff \#\{ c \in \Sigma^{f(|x|)}: (x,c) \in A \} \not\equiv 0 \pmod{2}\bigr]\end{array} \right\}\right.$

• Operator $\oplus$ jest podobny do operatora $\exists$ pod tym względem, że $\oplus\mathbf C$ dotyczy liczby istniejących certyfikatów, które są weryfikowalne w klasie $\mathbf C$ , ale zamiast tego zlicza liczbę certyfikatów modulo $2$ . Można tego użyć do zdefiniowania klas $\mathsf{\oplus P}$ i $\mathsf{\oplus L}$ . Podobne operatorzy " $\mathsf{Mod_k \cdot}$ " istnieją dla innych modułów $k$ .

$\mathsf{co}\mathbf C := \Bigl\{ L \subseteq \Sigma^\ast \,\Big|\, \exists A \in \mathbf C \;\forall x \in \Sigma^\ast: \bigl[x \in L \iff x \notin A \bigr] \Bigr\}$

• Jest to operator komplementarny i jest milcząco używany do definiowania , , oraz wielu innych klas z tych, o których nie wiadomo, że są zamknięte w ramach uzupełnień.c o N P c o C = P c o M o d k$\mathsf{ coNP}$$\mathsf{coC_=P}$$\mathsf{coMod_kL}$

$\mathsf{BP}\cdot\mathbf C := \left\{ (\Pi_0, \Pi_1) \,\left|\, \begin{array}{l} \Pi_0, \Pi_1 \subseteq \Sigma^\ast \;\mathbin\&\; \exists A \in \mathbf C \; \exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\ \quad\left[\begin{array}{l} \bigl(x \in \Pi_0 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \leqslant \tfrac{1}{3} {|\Sigma^{f(|x|)}|} \bigr) \mathbin\& \\ \bigl(x \in \Pi_1 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \geqslant \tfrac{2}{3} {|\Sigma^{f(|x|)}|} \bigr) \end{array}\right]\end{array}\right\}\right.$

- z przeprosinami za odstępy

• Operator najwyraźniej został wprowadzony przez Schöninga [2], ale w celu zdefiniowania języków (tj. Nie zezwolił na lukę prawdopodobieństwa) i bez użycia jawnych stałych lub . Definicja tutaj powoduje problemy z obietnicą, z wystąpieniami YES i NO-wystąpień w . Zauważ, że i ; operator ten był używany przez Todę i Ogiwarę [3], aby pokazać, że .$\mathsf{BP}$$\tfrac{1}{3}$$\frac{2}{3}$$\Pi_1$$\Pi_0$$\mathsf{BPP = BP\cdot P}$$\mathsf{AM = BP\cdot NP}$$\mathsf{P^{\#P} \subseteq BP\cdot\oplus P}$

Uwagi

Innymi ważnymi operatorami, które można wyodrębnić z definicji klas standardowych, są (z klas i ) i (z klas i ). W większości literatury zakłada się również, że (uzyskiwanie problemów funkcji z klas decyzyjnych) i (uzyskiwanie klas zliczania z klas decyzyjnych) są również operatorami złożoności.$\mathsf{C_= \cdot\mathbf C}$$\mathsf{C_= P}$$\mathsf{C_= L}$$\mathsf C\cdot\mathbf C$$\mathsf{PP}$$\mathsf{PL}$$\mathsf{F\cdot}$$\#\cdot$

Istnieje artykuł Borcherta i Silvestri [4], w którym zaproponowano zdefiniowanie operatora dla każdej klasy, ale wydaje się, że w literaturze niewiele się o nim mówi; Martwię się również, że takie ogólne podejście może mieć subtelne problemy definicyjne. Z kolei odnoszą się do dobrej prezentacji Köblera, Schöninga i Torána [5], która ma jednak już ponad 20 lat i wydaje się, że tęskni za .$\oplus$

Pytanie

Jaka książka lub artykuł jest dobrym źródłem informacji dla operatorów klasy złożoności?

Bibliografia

[1]: K. Wagner, Złożoność problemów kombinatorycznych z zwięzłymi reprezentacjami danych wejściowych , Acta Inform. 23 (1986) 325–356.

[2]: U. Schöning, Probabilistyczne klasy złożoności i lowness , w Proc. 2. konferencja IEEE nt. Struktury w teorii złożoności, 1987, s. 2-8; także w J. Comput. System Sci., 39 (1989), s. 84–100.

[3]: S. Toda i M. Ogiwara, Liczenie klas jest co najmniej tak trudne, jak hierarchia czasu wielomianowego , SIAM J. Comput. 21 (1992) 316–328.

[4]: B. i Borchert, R. Silvestri, operatory kropkowe, Theoretical Computer Science tom 262 (2001), 501–523.

[5]: J. Köbler, U. Schöning i J. Torán, The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, Basel (1993).

Oto odniesienie z wieloma definicjami operatorów (choć niewiele szczegółów):

S. Zachos i A. Pagourtzis, Złożoność kombinacyjna: operatory na klasach złożoności , postępowanie czwartego sympozjum logiki panhellenicznej (PLS 2003), Saloniki, 7-10 lipca 2003.

• Definiuje operator tożsamości , a także operatorów -, (odpowiadający powyżej), , (odpowiadający ograniczonemu jeden- błąd jednostronny), , (odpowiadający niedeterminizmowi z unikalnym przejściem akceptującym), (odpowiadający nieograniczonemu dwustronnemu błędowi) i (które dla klasy tworzy ).$\mathcal E$$\mathsf{co}$$\mathsf{N}$$\exists$$\mathsf{BP}$$\mathsf{R}$$\oplus$$\mathsf U$$\mathsf P$$\Delta$$\mathbf C$$\mathbf C \cap \mathsf{co}\mathbf C$

• To pokazuje że:

  1. $\mathcal E$ jest elementem tożsamości w odniesieniu do składu [Definicja 1];
  2. $\mathsf{co}$ - jest samo-odwrotny [Definicja 2];
  3. $\mathsf{N}$ jest idempotentny [Definicja 3] - domyślnie jest tak, że , , , i są również idempotentni;$\mathsf{BP}$$\mathsf{R}$$\oplus$$\mathsf U$$\mathsf{P}$
  4. $\mathsf{BP}$ i dojeżdżają do pracy z - [Definicje 4 i 8], podczas gdy jest niezmienny we właściwym składzie z - [Definicja 6];$\mathsf{P}$$\mathsf{co}$$\oplus$$\mathsf{co}$
  5. Powyższe operatory są monotoniczne (to znaczy dla wszystkich operatorów powyżej) :${\mathbf C_1 \subseteq \mathbf C_2} \implies {\mathcal O\cdot\mathbf C_1 \subseteq \mathcal O\cdot\mathbf C_2}$$\mathcal O$

W całym dokumencie opisano także kilka sposobów, w jakie operatorzy ci odnoszą się do tradycyjnych klas złożoności, takich jak , , , itp.$\mathsf{\Sigma^p_2 P}$$\mathsf{ZPP}$$\mathsf{AM}$$\mathsf{MA}$

Jako wstępne odniesienie do pojęcia operatora złożoności (i demonstrującego niektóre zastosowania tego pomysłu), najlepsze, co do tej pory znalazłem, to

D. Kozen, Theory of Computation (Springer 2006)

który pochodzi z notatek z wykładów na temat złożoności obliczeniowej i pokrewnych tematów. Na stronie 187 („Wykład uzupełniający G: Twierdzenie Tody”) definiuje operatory

• R (dla losowych certyfikatów z ograniczonym jednostronnym błędem, jak w klasie R P )$\mathsf R$$\mathsf{RP}$
• B P (dla losowych certyfikatów z ograniczonym błędem dwustronnym, patrz wyżej)$\mathsf{BP}$
• P (dla losowych certyfikatów z nieograniczonym błędem, por. C w uwagach powyżej)$\mathsf P$$\mathsf C$
• ⊕ (nieparzysta liczba certyfikatów, patrz wyżej)$\oplus$
• Σ P (istnienia certyfikatów wielomian długości CF ∃ wyżej)$\Sigma^{\mathrm{p}}$$\exists$
• Σ l O g (w przypadku istnienia O ( log n ) certyfikatów -długość CF ∃ powyżej)$\Sigma^{\mathrm{log}}$$O(\log n)$$\exists$
• Π p i Π l o g (operatory uzupełniające do Σ p i Σ l o g : patrz uwagi do ∀ powyżej)$\Pi^{\mathrm{p}}$$\Pi^{\mathrm{log}}$$\Sigma^{\mathrm{p}}$$\Sigma^{\mathrm{log}}$$\forall$
• # (definiowanie klasy liczącej, patrz uwagi powyżej)$\#$

i milcząco definiuje c o - na stronie 12 w zwykły sposób.$\mathsf{co\text-}$

Traktowanie tych operatorów przez Kozen'a wystarczy, aby wskazać, w jaki sposób są one powiązane z „zwykłymi” klasami złożoności i opisać twierdzenie Tody, ale niewiele mówi o ich relacjach i wspomina o nich tylko na 6 stronach (na końcu książka na znacznie szerszy temat). Mam nadzieję, że ktoś może podać lepsze odniesienie niż to.