Eine gute Referenz für Komplexitätsklassenoperatoren?

Ich bin daran interessiert, ob es gute Expository-Artikel oder Umfragen gibt, auf die ich mich beziehen kann, wenn ich über Komplexitätsklassenoperatoren schreibe : Operatoren, die Komplexitätsklassen transformieren, indem sie ihnen beispielsweise Quantifizierer hinzufügen.

Beispiele für Operatoren

Das Folgende kann als eine minimale Liste von Operatoren interpretiert werden, die eine Antwort beschreiben kann. Hier $\mathbf C$ ist eine beliebige Menge von Sprachen, über ein beliebiges endliches Alphabet $\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.$

• Der Operator $\exists$ wurde offenbar von Wagner [1] eingeführt, allerdings mit der Notation $\bigvee\! \mathbf C$ statt$\exists \mathbf C$ . Das bekannteste Beispiel einer Klasse auf diese Weise aufgebaut ist$\mathsf{NP} = \exists \mathsf P$ . Dieser Operator wird mit einem komplementären quantifier$\forall$ , in dem die$\exists c$ in der Definition ersetzt$\forall c$ , den man die gesamte Polynom Hierarchie leicht definieren kann: zum Beispiel$\mathsf{\Sigma_2^P P = \exists \forall P}$ . Dies ist möglicherweise der erste definierte Operator.

$\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.$

• The $\oplus$ operator is similar to the $\exists$ operator in that $\oplus\mathbf C$ concerns the number of certificates which exist that are verifiable in the class $\mathbf C$, but instead counts the number of certficiates modulo $2$. This can be used to define the classes $\mathsf{\oplus P}$ and $\mathsf{\oplus L}$. Similar operators "$\mathsf{Mod_k \cdot}$" exist for other moduli $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\}$

• Dies ist der komplementäre Operator und wird stillschweigend verwendet, um c o N P , c o C = P , c o M o d k L und eine Vielzahl anderer Klassen aus solchen zu definieren, von denen nicht bekannt ist, dass sie unter Komplementen geschlossen sind.$\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.$

— with apologies for the spacing

• The $\mathsf{BP}$ operator was apparently introduced by Schöning [2], albeit to define languages (i.e. he did not permit a probability gap) and without using the explicit constants $\tfrac{1}{3}$ or $\frac{2}{3}$. The definition here yields promise-problems instead, with YES-instances $\Pi_1$ and NO-instances in $\Pi_0$. Note that $\mathsf{BPP = BP\cdot P}$, and $\mathsf{AM = BP\cdot NP}$; this operator was used by Toda and Ogiwara [3] to show that $\mathsf{P^{\#P} \subseteq BP\cdot\oplus P}$.

Remarks

Andere wichtige Operatoren, die man aus den Definitionen der Standardklassen abstrahieren kann, sind C = ⋅ C (aus den Klassen C = P und C = L ) und C ⋅ C (aus den Klassen P P und P L ). In den meisten Literaturstellen ist auch implizit enthalten, dass F ⋅ (sich aus Entscheidungsklassen ergebende Funktionsprobleme) und # ⋅ (sich aus Entscheidungsklassen ergebende Zählklassen) ebenfalls Komplexitätsoperatoren sind.$\mathsf{C_= \cdot\mathbf C}$$\mathsf{C_= P}$$\mathsf{C_= L}$$\mathsf C\cdot\mathbf C$$\mathsf{PP}$$\mathsf{PL}$$\mathsf{F\cdot}$$\#\cdot$

Es gibt einen Artikel von Borchert und Silvestri [4], der vorschlägt, einen Operator für jede Klasse zu definieren, auf den in der Literatur jedoch nicht viel Bezug zu nehmen scheint. Ich mache mir auch Sorgen, dass solch ein allgemeiner Ansatz subtile Definitionsprobleme haben könnte. Sie verweisen wiederum auf eine gute Präsentation von Köbler, Schöning und Torán [5], die mittlerweile über 20 Jahre alt ist und auch zu versäumen scheint ⊕ .$\oplus$

Frage

Welches Buch oder welcher Artikel ist eine gute Referenz für Komplexitätsklassenoperatoren?

Verweise

[1]: K. Wagner, Die Komplexität kombinatorischer Probleme mit prägnanten Eingabedarstellungen , Acta Inform. 23 (1986) 325–356.

[2]: U. Schöning, Probabilistische Komplexitätsklassen und Lowness , in Proc. 2. IEEE-Konferenz über Struktur in der Komplexitätstheorie, 1987, S. 2-8; auch in J. Comput. System Sci., 39 (1989), S. 84-100.

[3]: S. Toda und M. Ogiwara, Zählklassen sind mindestens so schwer wie die Hierarchie der Polynomzeit , SIAM J. Comput. 21 (1992) 316–328.

[4]: B. und Borchert, R. Silvestri, Punktoperatoren , Theoretical Computer Science Volume 262 (2001), 501–523.

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

Hier ist eine Referenz mit vielen Definitionen von Operatoren (allerdings nicht viele Details):

S. Zachos und A. Pagourtzis, Kombinatorische Komplexität: Operatoren in Komplexitätsklassen , Proceedings of 4th Panhellenic Logic Symposium (PLS 2003), Thessaloniki, 7.-10. Juli 2003.

• Es definiert einen Identitätsoperator E sowie Operatoren c o -, N (entsprechend ∃ oben), B P , R (entsprechend einem begrenzten einseitigen Fehler), ⊕ , U (entsprechend einem Nichtdeterminismus mit einer eindeutigen Annahme Übergang), P (entsprechend unbeschränkte zweiseitige Fehler) und Δ (die für eine Klasse C Formen C ∩ c o C ).$\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$

• Es zeigt, dass:

  1. E ist ein Identitätselement in Bezug auf die Zusammensetzung [Definition 1];$\mathcal E$
  2. c o - ist selbstinvers [Definition 2];$\mathsf{co}$
  3. N ist idempotent [Definition 3] - implizit ist dies B P , R ,$\mathsf{N}$$\mathsf{BP}$$\mathsf{R}$$\oplus$ , U und P ebenfalls idempotent;$\mathsf U$$\mathsf{P}$
  4. B P und P pendeln mit c $\mathsf{BP}$$\mathsf{P}$$\mathsf{co}$ - [Definitionen 4 und 8], während ⊕ bei rechter Komposition mit c o - [Definition 6] unveränderlich ist ;$\oplus$$\mathsf{co}$
  5. Die oben genannten Operatoren sind alle monotone (das heißt, C 1 ⊆ C 2⟹O ⋅ C 1 ⊆ O ⋅ C 2 für alle oben genannten Operatoren O ):${\mathbf C_1 \subseteq \mathbf C_2} \implies {\mathcal O\cdot\mathbf C_1 \subseteq \mathcal O\cdot\mathbf C_2}$$\mathcal O$

Außerdem werden eine Reihe von Möglichkeiten beschrieben, wie sich diese Operatoren auf traditionelle Komplexitätsklassen beziehen, z. B. Σ p 2 P , Z P P , A M , M A usw.$\mathsf{\Sigma^p_2 P}$$\mathsf{ZPP}$$\mathsf{AM}$$\mathsf{MA}$

Als einleitender Verweis auf den Begriff des Komplexitätsoperators (und zur Demonstration einiger Anwendungen der Idee) ist das Beste, was ich bisher gefunden habe, das Beste

D. Kozen, Theorie der Berechnung (Springer 2006)

das aus Vorlesungsskripten über die Komplexität von Berechnungen und verwandte Themen abgeleitet wird. Auf Seite 187 ("Zusatzvorlesung G: Todas Theorem") definiert er die Operatoren

• R (für zufällige Zertifikate mit beschränktem einseitigem Fehler, wie in der Klasse R $\mathsf R$$\mathsf{RP}$ )
• $\mathsf{BP}$ (für zufällige Zertifikate mit begrenztem zweiseitigem Fehler, siehe oben)
• P (für zufällige Zertifikate mit unbegrenztem Fehler, vgl.$\mathsf P$$\mathsf C$ in den obigen Ausführungen)
• $\oplus$ (für eine ungerade Anzahl von Zertifikaten siehe oben)
• Σ p (für das Vorhandensein von Zertifikaten polynomialer Länge, siehe ∃ oben)$\Sigma^{\mathrm{p}}$$\exists$
• Σ l o g (fürExistenz von O ( log n ) -Länge Zertifikate, CF ∃ oben)$\Sigma^{\mathrm{log}}$$O(\log n)$$\exists$
• Π p und Π l o g (complementary Operatoren Σ p und Σ l o g : siehe Bemerkungen auf ∀ oben)$\Pi^{\mathrm{p}}$$\Pi^{\mathrm{log}}$$\Sigma^{\mathrm{p}}$$\Sigma^{\mathrm{log}}$$\forall$
• # (Definition einer Zählklasse, siehe oben)$\#$

und definiert stillschweigend c o - auf Seite 12 auf die übliche Weise.$\mathsf{co\text-}$

Kozens Behandlung dieser Operatoren reicht aus, um zu zeigen, wie sie mit den "üblichen" Komplexitätsklassen verbunden sind, und um Todas Theorem zu beschreiben, erörtert jedoch nicht viel ihre Beziehungen und erwähnt sie nur für insgesamt 6 Seiten (im Übrigen ein Buch, das ein viel breiteres Thema behandelt). Hoffentlich kann jemand eine bessere Referenz liefern.