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 .C
∃ C : = { L ⊆ Σ ∗|∃ A ∈ C.∃ f ∈ O ( p o l y ( n ) )∀ x ∈ Σ ∗ :[ x∈L⟺∃ c ∈ Σ f ( | x | ) : ( x , c ) ∈ A ] }
∃C:={L⊆Σ∗∣∣∣∃A∈C∃f∈O(poly(n))∀x∈Σ∗:[x∈L⟺∃c∈Σf(|x|):(x,c)∈A]}
- 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.∃
∃ ⋁C⋁C ∃ C∃C N P = ∃ PNP=∃P ∀∀ ∃ c∃c ∀ c∀c Σ P 2 P = ∃ ∀ PΣP2P=∃∀P
⊕ C : = { L ⊆ Σ ∗|∃ A ∈ C.∃ f ∈ O ( p o l y ( n ) )∀ x ∈ Σ ∗ :[ x∈L⟺# { c ∈ Σ f ( | x | ) : ( x , c ) ∈ A } ≢ 0( mod2 ) ] }
⊕C:={L⊆Σ∗∣∣∣∃A∈C∃f∈O(poly(n))∀x∈Σ∗:[x∈L⟺#{c∈Σf(|x|):(x,c)∈A}≢0(mod2)]}
- Operator ⊕
⊕ jest podobny do operatora ∃∃ pod tym względem, że ⊕ C.⊕C dotyczy liczby istniejących certyfikatów, które są weryfikowalne w klasie doC , ale zamiast tego zlicza liczbę certyfikatów modulo 2)2 . Można tego użyć do zdefiniowania klas ⊕ P.⊕P i ⊕ L.⊕L . Podobne operatorzy " M o d k ⋅Modk⋅ " istnieją dla innych modułów kk .
c o C : = { L ⊆ Σ ∗|∃ A ∈ C.∀ x ∈ Σ ∗ : [ x ∈ L⟺x ∉ A ] }
coC:={L⊆Σ∗∣∣∃A∈C∀x∈Σ∗:[x∈L⟺x∉A]}
- 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 L
coNP coC=P coModkL
B P ⋅ C : = { ( Π 0 , Π 1 )|Π 0 , Π 1 ⊆ Σ ∗I∃ A ∈ C.∃ f ∈ O ( p o l y ( n ) )∀ x ∈ Σ ∗ :[ ( x ∈ Π 0 ⇔ # { c ∈ Σ f ( | x | ) : ( x , c ) ∈ A } ⩽ 13|Σf(|x|)|)&(x∈Π1⇔#{c∈Σf(|x|):(x,c)∈A}⩾23|Σf(|x|)|)]}
BP⋅C:=⎧⎩⎨⎪⎪⎪⎪(Π0,Π1)∣∣∣∣∣Π0,Π1⊆Σ∗&∃A∈C∃f∈O(poly(n))∀x∈Σ∗:[(x∈Π0⇔#{c∈Σf(|x|):(x,c)∈A}⩽13|Σf(|x|)|)&(x∈Π1⇔#{c∈Σf(|x|):(x,c)∈A}⩾23|Σf(|x|)|)]⎫⎭⎬⎪⎪⎪⎪
- 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 .BP
BP 1313 2323 Π1Π1 Π0Π0 BPP=BP⋅PBPP=BP⋅P AM=BP⋅NPAM=BP⋅NP P#P⊆BP⋅⊕PP#P⊆BP⋅⊕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.C=⋅C
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 .⊕
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).