Dalam film Inception Cobb meminta Ariadne untuk merancang labirin yang membutuhkan waktu dua kali lebih banyak untuk merancang. Ini cocok untuk masalah umum di mana kita memiliki situasi di mana kita terbatas sumber daya dengan jumlah tertentu dan siapa pun yang akan memverifikasi bahwa masalah ini berada dalam kelas kompleksitas yang diberikan akan mengambil lebih banyak waktu dan atau ruang untuk menyelesaikannya. Apakah ini masalah baru?
Jawaban:
Situasi ini sering muncul di crypto, di mana Anda ingin membuat contoh masalah yang sulit bersama dengan solusi mereka. Sebagai contoh, ada karya Eric Bach (dan kemudian, Adam Kalai) untuk secara efisien menghasilkan bilangan bulat acak dengan faktorisasi utama mereka.
Salah satu dari banyak pengamatan menarik dari Impagliazzo dan Wigderson (Keacakan vs waktu: derandomisasi dengan asumsi yang seragam. J. Comput. Syst. Sci., 63: 672-688, 2001) adalah bahwa seseorang dapat secara efisien menghasilkan matriks acak seragam yang seragam bersama dengan permanen mereka. (Pikirkan tentang hal itu ... gunakan reducibilitas diri permanen ....) Selain itu, kita tahu bahwa permanen itu dapat direduksi sendiri secara acak . Jadi ini adalah contoh dari masalah yang sangat sulit dimana kita dapat secara efisien menghasilkan instance yang diselesaikan.
sumber
Pertama, saya tidak berpikir protokol Arthur-Merlin harus memasukkan model - itu terdengar dari motivasi seperti Anda hanya ingin menghasilkan contoh masalah dengan cepat sehingga algoritma untuk menyelesaikannya lambat. Dengan kata lain, jika kita dapat membuktikan bahwa Arthur dapat menghasilkan masalah yang sulit, maka tampaknya tidak perlu bagi Merlin untuk memverifikasi bahwa masalah yang dihasilkan sulit.
Sangat terkait adalah pertanyaan ini : Bisakah kita menghasilkan dalam waktu polinomial bahasa yang tidak dapat ditentukan dalam waktu polinomial? Jawabannya ternyata ya jika P unary tidak sama dengan NP unary.
sumber