Bukti bahwa masalah Grafik isomorfisma tidak

Masalah grafik isomorfisme adalah salah satu masalah berdiri terpanjang yang menolak klasifikasi ke dalam masalah atau N P- complete. Kami memiliki bukti bahwa hal itu tidak bisa N P -Lengkap. Pertama, Graph Isomorphism tidak bisa menjadi N P -complete kecuali hierarki polinomial [1] runtuh ke level kedua. Juga, penghitungan [2] versi GI adalah polinomial-time Turing yang setara dengan versi keputusannya yang tidak berlaku untuk masalah N P -complete yang diketahui . Versi penghitungan N P masalah -Lengkap tampaknya memiliki kompleksitas yang jauh lebih tinggi. Akhirnya, hasil rendahnya [3] GI sehubungan dengan P P ($P$$NP$$NP$$NP$$NP$$NP$$PP$ ) tidak diketahui memiliki masalah N P -complete. Hasil rendahnya GI telah ditingkatkan menjadi S P P G I = S P P setelah Arvind dan Kurur membuktikan bahwa GI berada di S P P [4].$PP^{GI}=PP$$NP$$SPP^{GI}=SPP$$SPP$

Apa yang lainnya (terakhir) hasil dapat memberikan bukti lebih lanjut bahwa GI tidak bisa -Lengkap?$NP$

Saya memposting pertanyaan di Mathoverflow tanpa mendapatkan jawaban.

[1]: Uwe Schöning, "Grafik isomorfisme berada dalam hierarki yang rendah", Prosiding Simposium Tahunan ke-4 tentang Aspek Teoretis Ilmu Komputer, 1987, 114-124

[2]: R. Mathon, "Catatan pada grafik masalah penghitungan isomorfisme", Information Processing Letters, 8 (1979) hal. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Grafik isomorfisme rendah untuk PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind dan P. Kurur. Grafik isomorfisma ada di SPP, ECCC TR02-037, 2002.

$GI$$QP$$GI$$NP$$NP\subseteq QP=DTIME(n^{polylog\, n})$$EXP=NEXP$$EXP\neq NEXP$$GI$$NP$