Terinspirasi oleh pertanyaan adalah faktor yang dikenal sebagai P-hard , saya bertanya-tanya seperti apa pengetahuan saat ini tentang kekerasan grafik isomorfisme. Saya yakin bahwa saat ini tidak diketahui apakah GI ada di P, tetapi:
apa kelas terbesar yang saat ini diketahui bahwa GI lebih sulit daripada?
(tidak dijawab pada pertanyaan yang terdengar serupa )
Untuk mengatasi beberapa komentar, saya ingin tahu kelas maksimal yang saat ini dikenal sebagai GI, masalahnya selesai. Algoritma yang dikenal untuk GI dibatasi oleh fungsi superpolinomial, dan merupakan anggota NP. Tetapi tidak diketahui bahwa GI adalah P-keras. Saya ingin tahu kelas C yang dikenal sebagai C-hard, dan semoga inklusif mungkin.
Jawaban:
Tampaknya ini adalah hasil kekerasan terkuat hingga saat ini.
sumber