Języki

12

Jakie inne ~~problemy występują w~~ językach innych niż izomorfizm grafów w ? Czy możesz podać jakieś referencje? $NP\cap coAM$

Aktualizacja: Zapomniałem wspomnieć, że jestem zainteresowany w językach nie wiadomo, że w . $coNP$

— Marcos Villagra
źródło

Masz na myśli tych, którzy nie są znane być w

, prawda?

c o N P

$\mathrm{coNP}$

— ilyaraz,

tak, zapomniałem wspomnieć, że

— Marcos Villagra,

Jest jednak uważa się , że

, więc najlepszym sposobem formułowania pytanie jest zastąpienie uważa się za znane. Przepraszam za mój pedantyzm.

c o N P = c o A M

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

— ilyaraz,

10

Jedyne inne, o których wiem, to problemy z izomorfizmem: izomorfizm grupowy i izomorfizm pierścieniowy. W protokoły dla obu z nich jest w zasadzie taka sama jak na wykresie izomorfizmie. $coAM$

Grupowy izomorfizm redukuje się do grafu. Izomorfizm redukuje się do izomorfizmu pierścieniowego.

$P$

— Joshua Grochow
źródło

9

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

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

— MRA
źródło

2

Są to problemy z wyszukiwaniem, a nie problemy decyzyjne, a warianty decyzyjne problemów aproksymacyjnych są problemami obiecującymi. Andy Drucker i ja mieliśmy podobną dyskusję na temat SVP i CVP na cstheory.stackexchange.com/questions/330/... "

— Joshua

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}$

Złożoność idealnej zerowej wiedzy

Statystyczne języki zerowej wiedzy można rozpoznać w dwóch rundach

$\mathbf{SZK}$

— MS Dousti
źródło