Masalah dugaan tetapi tidak terbukti mudah

Kami memiliki banyak masalah, seperti faktorisasi, yang sangat dugaan, tetapi tidak terbukti, berada di luar P. Apakah ada pertanyaan dengan properti yang berlawanan, yaitu, bahwa mereka sangat dugaan tetapi tidak terbukti berada di dalam P?

Dua dekade lalu, salah satu jawaban yang masuk akal akan menjadi pengujian primality : ada algoritma yang berjalan dalam waktu polinomial acak, dan algoritma yang berjalan dalam waktu polinom deterministik di bawah dugaan teori jumlah-bilangan yang masuk akal, tetapi tidak ada algoritma polinomial-waktu deterministik yang diketahui. Pada tahun 2002, itu berubah dengan hasil terobosan oleh Agrawal, Kayal, dan Saxena bahwa pengujian primality ada di P. Jadi, kita tidak bisa lagi menggunakan contoh itu.

Saya akan menempatkan pengujian identitas polinomial sebagai contoh masalah yang memiliki peluang bagus untuk berada di P, tetapi di mana tidak ada yang bisa membuktikannya. Kita tahu tentang algoritma waktu polinomial acak untuk pengujian identitas polinomial, tetapi tidak ada algoritma deterministik. Namun, ada alasan yang masuk akal untuk meyakini bahwa algoritma acak dapat derandomized.

Misalnya, dalam kriptografi, sangat diyakini bahwa ada generator pseudorandom yang sangat aman (misalnya, AES-CTR adalah salah satu kandidat yang masuk akal). Dan jika itu benar, maka pengujian identitas polinomial harus dalam P. (Misalnya, gunakan seed tetap, terapkan generator pseudorandom, dan gunakan outputnya sebagai pengganti bit acak; akan membutuhkan konspirasi yang sangat besar untuk gagal. ) Ini dapat dibuat formal menggunakan model oracle acak; jika kita memiliki fungsi hash yang dapat dimodelkan secara tepat oleh model oracle acak, maka itu mengikuti bahwa ada algoritma polinomial-waktu deterministik untuk pengujian identitas polinomial.

Untuk penjelasan lebih lanjut dari argumen ini, lihat juga jawaban saya pada subjek terkait dan komentar saya pada pertanyaan terkait .

$P=NP$

$P$

Tetapi, sekali lagi, tidak ada yang benar-benar tahu.

$P$$P$$P$

$\sf NP\cap coNP$$e^{O(\sqrt{n})}$$n$$\sf P$