Langues

12

Quels sont les autres langages de ~~problèmes~~ différents de l'isomorphisme des graphes dans ? Pouvez-vous donner quelques références? $NP\cap coAM$

Mise à jour: J'ai oublié de mentionner que je suis intéressé dans les langues ne sont pas connus pour être en . $coNP$

cc.complexity-theory reference-request complexity-classes graph-isomorphism Marcos Villagra
la source

Vous voulez dire que ceux-ci ne sont pas connus pour être en

, non?

c o N P

$\mathrm{coNP}$

ilyaraz

oui, j'ai oublié de le mentionner

Marcos Villagra

Mais on pense que

, donc la meilleure façon de formuler la question est de remplacer la croyance par connue. Désolé pour mon pédantisme.

c o N P = c o A M

$\mathrm{coNP} = \mathrm{coAM}$

ilyaraz

10

Les seuls autres que je connais sont également des problèmes d'isomorphisme: isomorphisme de groupe et isomorphisme en anneau. Les protocoles pour les deux sont essentiellement les mêmes que pour l'isomorphisme de graphe. $coAM$

L'isomorphisme de groupe se réduit à l'isomorphisme graphique se réduit à l'isomorphisme en anneau.

$P$

Joshua Grochow
la source

9

$O(\sqrt{n/\log(n)})$ $NP \cap coAM$ $n$ $coNP$

$O(\sqrt{n})$ $NP \cap coNP$

MRA
la source

2

Ce sont des problèmes de recherche, pas des problèmes de décision, et les variantes de décision des problèmes d'approximation sont des problèmes de promesse. Andy Drucker et moi avons eu une discussion similaire sur SVP et CVP sur cstheory.stackexchange.com/questions/330/… "

Joshua Grochow

6

$\mathbf{NP}\subseteq\mathbf{AM}$ $\mathbf{AM}\cap\mathbf{coAM}$ $\mathbf{PZK}\subseteq \mathbf{SZK}\subseteq \mathbf{AM}\cap\mathbf{coAM}$ $\mathbf{PZK}$ $\mathbf{SZK}$

La complexité d'une parfaite connaissance zéro

Les langues statistiques à connaissance zéro peuvent être reconnues en deux tours

$\mathbf{SZK}$

MS Dousti
la source

Langues

Réponses: