Fungsi yang dijamin satu arah jika ada fungsi satu arah?

13

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?

Timothy Chow
sumber
Hai Timothy Chow, mungkin Anda dapat membantu dan menunjuk ke tautan di mana trik untuk menuliskan algoritma, bahwa jika P = NP, memecahkan SAT dalam waktu polinomial, apakah diformalkan? Terima kasih banyak
Avi Tal
@AviTal Lihat contoh ini: scholarpedia.org/article/Universal_search
Vanessa

Jawaban:

11

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.

Bjørn Kjos-Hanssen
sumber
Terima kasih! Menggunakan Google Cendekia, saya dapat menggunakan referensi ini untuk menemukan referensi untuk cryptosystem kunci publik yang lengkap, oleh Grigoriev, Hirsch, dan Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12.
Timothy Chow
Bisakah Anda jelaskan detail fungsi ini? Seperti mengapa ia dibatalkan setelah langkah n ^ 2, mengapa 'menyimpan salinan awalan program dan memaksanya, serta panjang input, pada output' dan apa 'hanya di tempat-tempat di mana ekstensi yang mungkin seperti itu unik' berarti persis . Saya tidak tahu apakah ini layak mendapat pertanyaan terpisah.
galmeida
@ BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/…
galmeida