Un problème naturel dans

La classe de complexité est définie comme suit (à partir de Wikipedia ): $\textrm{S}_2^\textrm{P}$

Un langage est dans s'il existe un prédicat polynomial tel que $L$ $S_2^P$ $P$

Si , alors il existe un tel que pour tout , $x \in L$ $y$ $z$ $P(x,y,z)=1$

Si , alors il existe un tel que pour tout , $x \notin L$ $z$ $y$ $P(x,y,z)=0$

où la taille de et doit être polynomiale dans la taille de . $y$ $z$ $x$

Voir également le post de Fortnow et le zoo de la complexité pour des explications et des discussions plus informelles.

Bien que cette classe semble raisonnablement naturelle, je ne trouve pas d'exemple de problème qui se trouve dans pour une raison non triviale (c'est-à-dire, pas seulement parce qu'il est en NP ou MA ou une classe contenue dans ). Quelqu'un connaît-il un problème qui correspond à cette description? $\textrm{S}_2^\textrm{P}$ $\textrm{S}_2^\textrm{P}$

Si personne ne peut penser à un problème comme celui-là, cela ne me dérangerait pas un problème qui est dans une sous-classe de , mais ce n'est pas trivial de le montrer, alors que le problème est évidemment dans . $\textrm{S}_2^\textrm{P}$ $\textrm{S}_2^\textrm{P}$

cc.complexity-theory complexity-classes Robin Kothari
la source

Que diriez-vous "d'un nombre impair de ces circuits sont satisfaisables"?

$\;$

Ceci est un bel exemple, mais il est aussi dans la plus petite classe

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

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

sdcvvc

Pas tout à fait ce que vous avez demandé, mais qu'en est-il d'un problème complet pour promesse -

? Fortnow - Impagliazzo - Kabanets - Umans, On the complex of succinct zero-sum games, Computational Complexity 17: 353-376, 2008, voir cs.sfu.ca/~kabanets/Research/games.html

S_{2}^{p}

$\mathsf{S_2^p}$

Joshua Grochow

@RickyDemer: Merci, c'est un bel exemple. (Si je comprends bien, il est tout aussi facile de montrer que le problème est également en

)

Δ_{2}

$\Delta_2$

Robin Kothari

@JoshuaGrochow: Merci, cela fonctionne pour moi. N'hésitez pas à poster cela comme réponse. Cela semble être la meilleure réponse jusqu'à présent, mais j'attendrai de voir si j'en ai une meilleure.

Robin Kothari

Que diriez-vous d'un problème complet pour promesse - ? $\mathsf{S_2^p}$

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets et Chris Umans. Sur la complexité des jeux succincts à somme nulle . Complexité informatique 17: 353-376, 2008.

Du résumé:

Nous prouvons que l'approximation de la valeur d'un jeu succinct à somme nulle à l'intérieur d'un facteur additif est complète pour la classe promesse - , la version "promesse" de . À notre connaissance, c'est le premier problème naturel montré complet pour cette classe. $\mathsf{S_2^p}$ $\mathsf{S_2^p}$

(Note historique: il n'est pas trop surprenant que peu de problèmes naturels soient connus pour être dans mais pas connus pour être dans ses sous-classes ou Si vous consultez les documents originaux de Russell - Sundaram et Canetti (indépendamment), il semble que la définition de été faite plus ou moins spécifiquement pour capturer leurs arguments améliorés plaçant dans , plutôt que pour saisir un ensemble de problèmes naturels.) $\mathsf{S_2^p}$ $\mathsf{MA}$ $\mathsf{P^{NP}}$ $\mathsf{S_2^p}$ $\mathsf{BPP}$ $\mathsf{PH}$

Joshua Grochow
la source

Un problème naturel dans

Réponses: