Ada trik lama untuk menuliskan algoritma yang, jika P = NP, memecahkan SAT dalam waktu polinomial. Pada dasarnya, satu daftar semua mesin waktu polinomial dan multi-tugas di atasnya.
Apakah ada trik analog untuk fungsi satu arah (atau bahkan fungsi pintu jebakan satu arah)? Yaitu, dapatkah kita menuliskan fungsi yang, jika fungsi satu arah ada, adalah fungsi satu arah?
Tampaknya tidak ada cara mudah untuk meniru trik P = NP. Dalam hal itu, kita dapat dengan cepat mengenali solusi ketika kita mendapatkannya. Tetapi jika saya multi-tugas atas semua fungsi waktu polinomial, tidak ada cara yang jelas untuk mengenali fungsi satu arah ketika saya tiba di satu.
Jika jawaban atas pertanyaan di atas adalah tidak, adakah alasan mengapa kita tidak bisa melakukannya? Mungkin menuliskan fungsi seperti itu entah bagaimana akan membuktikan bahwa fungsi satu arah ada?
sumber
Jawaban:
Ya, fungsi semacam itu ditemukan oleh Levin sendiri, yang diterbitkan agak baru-baru ini:
Kisah fungsi satu arah . Masalah Transmisi Informasi (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.
sumber