S2P (złożoność)

W teorii złożoności obliczeniowej SP ^hierarchii
₂ jest klasą złożoności pośrednią między pierwszym a drugim poziomem wielomianów . Język L jest w, jeśli istnieje predykat czasu wielomianowego P taki, że ${\ Displaystyle {\ mathsf {S}} _ {2} ^ {P}}$

• $\ Displaystyle x \ in L}$ ∈ ${\ Displaystyle P (x, y, z) = 1}$ , to istnieje y takie, że dla wszystkich z , ,
• x ${\ Displaystyle x \ notin L}$ , to istnieje z takie że dla wszystkich y , ${\ Displaystyle P (x, y, z) = 0}$ ,

gdzie rozmiar y i z musi być wielomianem x .

Stosunek do innych klas złożoności

Z definicji wynika bezpośrednio, że SP
² _jest domknięty na sumy, przecięcia i dopełnienia. Porównując definicję z definicją z ${\ Displaystyle \ Sigma _ {2} ^ {P}}$ i ${\ Displaystyle \ Pi _ {2} ^ {P}}$ , wynika również od razu, że S
^P ₂ jest zawarty w ${\ Displaystyle \ Sigma _ {2} ^ {P} \ cap \ Pi _ {2} ^ {P}}$ . Włączenie to można w rzeczywistości wzmocnić do ZPP ^NP .

SP ²
_Każdy . język w NP należy również do Z definicji język L jest w NP wtedy i tylko wtedy, gdy istnieje wielomianowy weryfikator V ( x , y ), taki, że dla każdego x w L istnieje y , dla którego V odpowiada prawdzie, i taki, że dla każdego x nie w L , V zawsze odpowiada fałsz. Ale taki weryfikator można łatwo przekształcić w S
^P ₂ predykat P ( x , y , z ) dla tego samego języka, który ignoruje z i poza tym zachowuje się tak samo jak V . Z tego SP ^samego
₂ . Te proste inkluzje można wzmocnić, aby pokazać powodu co-NP należy do SP ^,
₂ że klasa zawiera MA (przez uogólnienie twierdzenia Sipsera – Lautemanna ) i ${\ Displaystyle \ Delta _ {2} ^ {P}}$ (bardziej ogólnie ${\ Displaystyle P ^ {{\ mathsf {S}} _ {2} ^ {P}} = { \mathsf {S}}_{2}^{P}} )$ .

Twierdzenie Karpa-Liptona

Wersja twierdzenia Karpa-Liptona stwierdza, że ​​jeśli każdy język w NP ma obwody o rozmiarach wielomianowych , to wielomianowa hierarchia czasu zapada się do
^SP ₂ . Ten wynik daje wzmocnienie Kannana : wiadomo, że SP
² _nie jest zawarte w SIZE ( n ^k ) dla żadnego ustalonego k .

Hierarchia symetryczna

$;$ można zdefiniować jako operator na klasach wtedy ${\ Displaystyle {\ mathsf {S}} _ {2} P = {\ mathsf {S}} _ {2} ^ {P}}$ . Iteracja $;$ daje „symetryczną hierarchię suma utworzonych w ten sposób klas jest równa hierarchii wielomianów .

• Canetti, Ran (1996). „Więcej o BPP i hierarchii czasu wielomianowego”. Listy dotyczące przetwarzania informacji . Elsevier. 57 (5): 237–241. doi : 10.1016/0020-0190(96)00016-6 .
•    Russell, Aleksander; Sundaram, Ravi (1998). „Symetryczna naprzemienność przechwytuje BPP” . Złożoność obliczeniowa . Birkäuser Verlag. 7 (2): 152–162. doi : 10.1007/s000370050007 . ISSN 1016-3328 . S2CID 15331219 .

Linki zewnętrzne

• Zoo złożoności : S ₂ P
• Klasa złożoności tygodnia: S ₂ ^P , Lance Fortnow , 28 sierpnia 2002 r.