Bahasa

Apa masalah lain yang berbeda dari bahasa isomorfisme grafik dalam ? Bisakah Anda memberikan beberapa referensi?$NP\cap coAM$

Update: Saya lupa menyebutkan bahwa saya tertarik dalam bahasa yang tidak dikenal berada di .$coNP$

Satu-satunya yang saya tahu adalah masalah isomorfisme: isomorfisme kelompok dan cincin isomorfisme. The protokol untuk kedua ini pada dasarnya sama dengan untuk grafik isomorfisma.$coAM$

Kelompok isomorfisma tereduksi menjadi graf isomorfisme tereduksi menjadi cincin isomorfisme.

$P$

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

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

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

Kompleksitas zero-knowledge yang sempurna

Statistik nol-pengetahuan bahasa dapat dikenali dalam dua putaran

$\mathbf{SZK}$