Generator kebal didefinisikan sebagai berikut:
Biarkan menjadi hubungan NP, dan menjadi mesin yang menerima . Secara tidak resmi, sebuah program adalah generator yang kebal jika, pada input , ia menghasilkan pasangan instance-saksi , dengan , menurut distribusi di mana setiap musuh waktu-polinomial yang diberikan gagal menemukan saksi bahwa , dengan probabilitas yang nyata, untuk panjang yang tak terhingga .M L ( R ) ( x , w ) ∈ R | x | = n x x ∈ S n
Generator kebal, pertama kali didefinisikan oleh Abadi et al. , menemukan banyak aplikasi dalam kriptografi.
Keberadaan generator yang kebal didasarkan pada asumsi bahwa , namun ini mungkin tidak cukup (lihat juga topik terkait ).
Teorema 3 dari Abadi et al. makalah, dikutip di atas, menunjukkan bahwa bukti keberadaan generator yang kebal tidak merelatifkan:
Teorema 3. Ada oracle sehingga , dan generator yang kebal tidak ada relatif terhadap B.P B ≠ N P B
Saya tidak mengerti bagian dari pembuktian teorema ini. Biarkan menunjukkan operasi serikat terpisah . Biarkan menjadi bahasa PSPACE-lengkap dari formula Boolean terukur yang memuaskan, dan biarkan menjadi serangkaian string dengan kompleksitas Kolmogorov maksimum yang sangat jarang. Secara khusus, berisi satu string dari setiap panjang , di mana urutan didefinisikan oleh: , adalah eksponensial dalam , untuk ; jika dan , laluK K n i n 1 , n 2 , … n 1 = 2 n i n i - 1 i > 1 x ∈ K | x | = n x nmemiliki kompleksitas Kolmogorov .
Makalah ini menyatakan bahwa relatif terhadap , menyatakan bahwa . Bisakah Anda jelaskan? (Juga, tolong jelaskan apakah bersifat rekursif.)P ≠ N P B
sumber