Apakah ada jenis perbedaan hasil amplifikasi untuk Masalah Grafik Isomorfisme?

Misalkan dan adalah dua grafik tidak berarah pada set simpul . isomorfik jika dan hanya jika ada permutasi sedemikian sehingga , atau lebih resmi, jika ada permutasi sedemikian sehingga adalah ujung dalam jika dan hanya jika adalah keunggulan dalam . Masalah Grafik Isomorfisme adalah masalah memutuskan apakah dua grafik yang diberikan adalah isomorfik.$G_1$$G_2$$\{1, \dotsc, n\}$$\Pi$$G_1 = \Pi(G_2)$$\Pi$$(i,j)$$G_1$$(\Pi(i),\Pi(j))$$G_2$

Apakah ada operasi pada grafik yang menghasilkan "amplifikasi celah" dengan gaya bukti Dinur tentang Teorema PCP ? Dengan kata lain, apakah ada transformasi waktu komputasi polinomial dari ke sehingga$(G_1,G_2)$$(G'_1,G'_2)$

• jika dan isomorfis, maka dan juga isomorfik, dan$G_1$$G_2$$G'_1$$G'_2$
• jika dan bukan isomorfik, maka untuk setiap permutasi , grafik adalah " -far" dari untuk beberapa konstanta kecil , di mana -far berarti bahwa jika kita memilih secara seragam secara acak, kemudian dengan probabilitas baik $G_1$$G_2$$\Pi$$G'_1$$\epsilon$$\Pi(G'_2)$$\epsilon$$\epsilon$$(i,j)$$\epsilon$
  • $(i,j)$ adalah tepi dari dan bukan tepi dari , atau$G'_1$$(\Pi(i),\Pi(j))$$G'_2$
  • $(i,j)$ bukan tepi dari dan adalah tepi dari .$G'_1$$(\Pi(i),\Pi(j))$$G'_2$

Saya tidak tahu apakah hal seperti itu bisa ada atau tidak. Tetapi menarik (dan mungkin tepat waktu) untuk mencatat bahwa "gap gap" seperti itu kemungkinan akan menyiratkan algoritma waktu quasipolynomial untuk isomorfisme grafik (berbeda dari yang baru diumumkan)

Dalam tulisan ini , algoritma perkiraan diberikan untuk masalah "MAX-PGI" untuk memaksimalkan pasangan tepi / non-tepi yang cocok; jika kita mengurangi dari GI menjadi "Gap-MAX-PGI", maka kita dapat memperkirakan untuk membedakan sisi mana dari celah yang kita gunakan.

Jadi, saya pikir bukti Dinur tentang teorema PCP tidak mungkin secara langsung dapat digeneralisasikan ke "penguat celah" seperti itu, mengingat rintangan yang harus diatasi.