Menggunakan hasil negatif untuk membuktikan hasil positif dalam teori komputasi

Banyak hasil dalam kriptografi bergantung pada hasil / dugaan ketidakmungkinan dalam teori kompleksitas. Sebagai contoh, kriptografi kunci publik menggunakan RSA diyakini dimungkinkan karena dugaan tentang tidak layaknya anjak piutang (dan masalah pencarian akar modular).

Pertanyaanku adalah :

apakah kita memiliki hasil yang serupa dalam teori komputabilitas? Apakah ada konstruksi positif yang menarik menggunakan hasil ketidakmungkinan negatif?

Misalnya, apakah ketidakpastian masalah penghentian memungkinkan kami untuk melakukan tugas yang tidak dapat kami lakukan jika masalah penghentian dapat ditentukan?

cc.complexity-theory cr.crypto-security computability Kaveh
sumber

Dua penggunaan utama hasil negatif dalam teori kompleksitas adalah (1) kriptografi dan (2) derandomisasi. Tidak satu pun dari ini berlaku dalam kerangka komputabilitas. Menguraikan kriptosistem yang dapat dikomputasi adalah tugas yang tidak dapat dihindari, dan fungsi apa pun yang dapat dikomputasi pada mesin Turing acak juga dapat dihitung pada mesin Turing deterministik (dengan cara yang konstruktif).

David Harris

ini tampaknya menjadi pertanyaan kata-kata. "Kriptografi kunci publik menggunakan RSA adalah mungkin" hanyalah cara setengah penuh untuk mengatakan "meretakkan RSA dalam waktu-poli adalah tidak mungkin". Saya tidak melihat bagaimana RSA adalah konstruksi positif ... itu hanya konstruksi, dan bukti keamanannya adalah hasil negatif tentang kemungkinan algoritma musuh.

Artem Kaznatcheev

@ Artem, intinya di sini adalah bahwa kita sedang membangun sebuah protokol yang dapat digunakan dan kondisi bahwa protokol tersebut berguna adalah hasil negatif bahwa tidak ada musuh yang dapat merusaknya. Secara intuitif apa yang saya maksud dengan hasil negatif adalah teorema yang mengatakan bahwa sesuatu tidak dapat dilakukan. Dengan hasil positif yang saya maksud adalah konstruksi yang memungkinkan melakukan beberapa tugas (misalnya komunikasi yang aman). Hasil positif mungkin memiliki hasil negatif di dalamnya. Saya akan berpikir tentang mengungkapkan ini secara lebih formal.

Kaveh

@ David, ya, saya tahu keduanya. Apakah Anda tahu ada penggunaan lain yang diketahui dari hasil negatif untuk hasil positif dalam teori kompleksitas / crypto?

Kaveh

Saya pribadi juga berpikir itu adalah masalah kata-kata. Misalnya, Anda dapat mengambil teorema Rice, dan mengatakan "untuk setiap antivirus, Anda dapat membuat virus yang tidak dikenali". Dalam setiap teorema ketidaklengkapan, Anda dapat mengubahnya menjadi "Anda dapat membuat contoh tandingan".

Ludovic Patey

Jawaban:

Dalam beberapa hal, inilah yang dimaksud dengan teori parametrik.

Abstraksi data adalah cara kami memastikan bahwa tidak ada klien modul yang dapat mengakses elemen-elemen modul kecuali sesuai dengan antarmuka yang terbuka oleh modul. Kami mengandalkan ini untuk memastikan bahwa invarian internal struktur data tidak dapat dipecah oleh klien modul - misalnya, jika Anda mengakses pohon yang seimbang hanya melalui antarmuka yang dipublikasikan, maka itu berarti bahwa pohon itu akan selalu seimbang.

Jadi kami menggunakan properti negatif - bahwa tidak ada klien yang mungkin dapat melanggar batas abstraksi - untuk menyimpulkan yang positif - yang selalu dipegang oleh invarian representasi data.

Neel Krishnaswami
sumber

Data diakses melalui oracle yang sesuai, tetapi itu tidak selalu berarti bahwa itu tidak dapat dihitung untuk mengaksesnya secara langsung

David Harris

Abstraksi data pada dasarnya adalah hasil yang dapat didefinisikan : dikatakan bahwa tidak ada program dalam bahasa pemrograman yang dapat menembus batas abstraksi. Jika Anda menggunakan mekanisme ekstra-linguistik (misalnya, Anda menjalankan debugger Anda), tentu saja Anda dapat melihat bidang pribadi apa yang dimiliki tabel hash.

Neel Krishnaswami

Kompleksitas Kolmogorov mungkin termasuk dalam kategori ini.

Satu dapat menunjukkan bahwa ada string tertentu, yang tidak dapat dikompresi oleh mesin Turing. String ini berperilaku "secara umum" sehingga Anda dapat mempelajari sifat acak dari informasi dan tugas komputasi tertentu dengan mempelajari perilaku sehubungan dengan string (non-acak) yang tidak dapat dimampatkan.

David Harris
sumber

Terima kasih, orang lain juga menyarankan ini dalam diskusi offline. (Saya tidak sepenuhnya yakin karena kita tidak benar-benar menggunakan string acak komputasi untuk melakukan tugas-tugas dunia nyata, ia memiliki lebih banyak rasa eksistensial daripada membangun sesuatu, saya mungkin harus berpikir sedikit lebih banyak tentang apa yang sebenarnya saya maksud dengan hasil positif .p: motivasi awal saya adalah untuk memberikan kepada siswa program sarjana teori pembelajaran komputer contoh tentang manfaat hasil negatif dalam membangun sesuatu untuk melakukan tugas-tugas dunia nyata.)

Kaveh

Sementara seseorang tidak (dan tidak bisa) membangun string yang tidak dapat dimampatkan dalam praktik, sangat umum untuk membangun string secara acak. Kemudian, dengan probabilitas tinggi, itu akan menjadi tidak tertekan.

David Harris