idiomas

12

Que outros ~~problemas de~~ linguagem diferentes do isomorfismo de grafos existem em ? Você pode dar algumas referências? $NP\cap coAM$

Update: Esqueci de mencionar que eu estou interessado em línguas desconhecidas para a . $coNP$

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

Você quer dizer que aqueles que não são conhecidos por serem em

, certo?

c o N P

$\mathrm{coNP}$

Ilyaraz 20/08

sim, eu esqueci de mencionar isso

Marcos Villagra

Mas é acreditado que

, de modo a melhor maneira de formular a questão é substituir acreditado por conhecido. Desculpe pelo meu pedantismo.

c o N P = c o A M

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

Ilyaraz 20/08

10

Os únicos outros que eu conheço são também problemas de isomorfismo: isomorfismo de grupo e isomorfismo em anel. Os protocolos para ambos são essencialmente os mesmos do isomorfismo gráfico. $coAM$

O isomorfismo de grupo reduz ao gráfico o isomorfismo reduz ao isomorfismo em anel.

$P$

Joshua Grochow
fonte

9

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

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

MRA
fonte

2

Esses são problemas de pesquisa, não de decisão, e as variantes de decisão dos problemas de aproximação são promissores. Andy Drucker e eu tivemos uma discussão semelhante sobre SVP e CVP em cstheory.stackexchange.com/questions/330/… "

Joshua Grochow 23/08/10

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

A complexidade do perfeito conhecimento zero

Linguagens estatísticas de conhecimento zero podem ser reconhecidas em duas rodadas

$\mathbf{SZK}$

MS Dousti
fonte

idiomas

Respostas: