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 jeśli istnieje predykat wielomianowy taki, że $L$ $S_2^P$ $P$

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

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

gdzie wielkość zarówno jak i musi być wielomianowa w rozmiarze . $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 ). 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 . $\textrm{S}_2^\textrm{P}$ $\textrm{S}_2^\textrm{P}$

cc.complexity-theory complexity-classes

— Robin Kothari
źródło

A może „nieparzysta liczba tych obwodów jest wystarczająca”?

$\;$

Jest dobrym przykładem, jest jednak również w mniejszym klasy

Δ_{2} = P^{N P}

$\Delta_2 = \mathsf{P}^{\mathsf{NP}}$

— sdcvvc

Nie do końca to, o co prosiłeś, ale co powiesz na problem z obietnicą -

? Fortnow - Impagliazzo - Kabanets - Umans, O złożoności zwięzłych gier o sumie zerowej, Złożoność obliczeniowa 17: 353-376, 2008, patrz: cs.sfu.ca/~kabanets/Research/games.html

S_{2}^{p}

$\mathsf{S_2^p}$

— Joshua

@RickyDemer: Dzięki, to dobry przykład. (Jeśli dobrze rozumiem, równie łatwo jest wykazać, że problem dotyczy również

Δ_{2}

$\Delta_2$

— Robin Kothari

@JoshuaGrochow: Dzięki, to działa dla mnie. Możesz to opublikować jako odpowiedź. To chyba najlepsza jak dotąd odpowiedź, ale poczekam, czy dostanę lepszą.

— Robin Kothari

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 . 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 lub Jeśli sprawdzisz oryginalne prace Russella - Sundaram i Canetti (samodzielnie), wydaje się, że definicja została wykonana mniej lub bardziej wyraźnie na lepsze przechwytywanie ich argumentów umieszczenie w 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}$

— Joshua Grochow
źródło