Naturalny problem w

Klasa złożoności jest zdefiniowana następująco (z Wikipedii ):$\textrm{S}_2^\textrm{P}$

Język znajduje się w S P 2, jeśli istnieje predykat P wielomianowy taki, że$L$$S_2^P$$P$

• Jeśli , to istnieje y takie, że dla wszystkich z , P ( x , y , z ) = $x \in L$$y$$z$$P(x,y,z)=1$
• Jeśli , to istnieje z takie, że dla wszystkich y , P ( x , y , z ) = $x \notin L$$z$$y$$P(x,y,z)=0$

gdzie wielkość zarówno jak i z musi być wielomianowa w rozmiarze x .$y$$z$$x$

Zobacz także post Fortnowa i zoo złożoności, aby uzyskać bardziej nieformalne wyjaśnienia i dyskusje.

Chociaż ta klasa wydaje się dość naturalna, nie mogę znaleźć przykładu problemu, który jest w z nie trywialnego powodu (tj. Nie tylko dlatego, że jest on w NP lub MA, albo w jakiejś klasie zawartej w S P 2 ). Czy ktoś zna problem, który pasuje do tego opisu?$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Jeśli nikt nie pomyśli o takim problemie, nie miałbym nic przeciwko problemowi, który należy do podklasy , ale pokazanie tego nie jest trywialne, podczas gdy problem oczywiście dotyczy S P 2 .$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

A co powiesz na problem z obietnicą - ?$\mathsf{S_2^p}$

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets i Chris Umans. O złożoności zwięzłych gier o sumie zerowej . Złożoność obliczeniowa 17: 353–376, 2008.

Z streszczenia:

Udowadniamy, że przybliżenie wartości zwięzłej gry o sumie zerowej do współczynnika addytywnego jest kompletne dla obietnicy klasy - , „obietnicy” wersji S p 2 . Według naszej najlepszej wiedzy jest to pierwszy naturalny problem pokazany jako kompletny dla tej klasy.$\mathsf{S_2^p}$$\mathsf{S_2^p}$

(Uwaga historyczna: nie jest zaskakujące, że niewiele naturalnych problemów występuje w ale nie wiadomo, że należą do jego podklas M A lub P N P. Jeśli sprawdzisz oryginalne prace Russella - Sundaram i Canetti (samodzielnie), wydaje się, że definicja S s 2 została wykonana mniej lub bardziej wyraźnie na lepsze przechwytywanie ich argumentów umieszczenie B P P w P H a nie uchwycić pewien zbiór z naturalnych problemów).$\mathsf{S_2^p}$$\mathsf{MA}$$\mathsf{P^{NP}}$$\mathsf{S_2^p}$$\mathsf{BPP}$$\mathsf{PH}$