Rastgeleleştirilmiş ve Etkileşimli Hesaplama
Algoritmaların yazı tura atmasına veya güçlü ancak güvenilmeyen bir kanıtlayıcı ile diyalog kurmasına izin vermek, BPP ve IP gibi karmaşıklık sınıfları ortaya çıkararak verimli doğrulamanın neler başarabileceğine dair anlayışımızı yeniden şekillendirmektedir.
Tanım
Rastgeleleştirilmiş hesaplama, bir makineyi rastgele bitlere erişimle donatmakta ve doğru bir cevabın olasılığını ölçmektedir; etkileşimli hesaplama ise polinom zamanlı bir doğrulayıcının bir kanıtlayıcı ile mesaj alışverişinde bulunmasına olanak tanımaktadır. Ortaya çıkan sınıflar, sınırlı hata ile çözülebilen veya etkileşim yoluyla doğrulanabilen problemleri içermektedir.
Kapsam
Bu konu, BPP, RP ve ZPP dahil olmak üzere olasılıksal karmaşıklık sınıflarını ve rastgeleliğin ortadan kaldırılıp kaldırılamayacağı sorusunu, etkileşimli kanıt sistemlerini ve IP'yi PSPACE ile özdeşleştiren teoremi, sıfır bilgi kanıtlarını ve yaklaşıklığın zorluğunun temelini oluşturan olasılıksal olarak kontrol edilebilir kanıtları kapsamaktadır.
Temel sorular
- Rastgeleliğe erişim, algoritmaların daha fazla problemi verimli bir şekilde çözmesine olanak tanımakta mıdır?
- Sınırlı bir doğrulayıcı, güvenilmeyen, güçlü bir kanıtlayıcı tarafından yapılan iddiaları kontrol edebilir mi?
- Bir ifadenin doğru olduğuna, başka hiçbir şey öğrenmeden nasıl ikna olunabilir?
- Etkileşimli ve olasılıksal kanıt kontrolü, yaklaştırmayı nasıl kısıtlamaktadır?
Temel kuramlar
- IP, PSPACE'e eşittir
- Polinom zamanlı bir doğrulayıcı ile her şeye gücü yeten bir kanıtlayıcı arasındaki etkileşimli bir protokol ile kanıtlanabilen diller, tam olarak polinom uzayında karar verilebilir olanlardır; bu, etkileşimin gücünün çarpıcı bir ölçüsüdür.
- PCP teoremi
- NP'deki her problemin, yalnızca sabit sayıda rastgele seçilmiş bit okunarak doğrulanabilen kanıtları bulunmaktadır; bu sonuç, birçok optimizasyon problemini yaklaştırmanın NP-zor olduğu kesin eşiği belirlemektedir.
Klinik önem
Bu fikirler doğrudan teknolojik etkiye sahiptir: sıfır bilgi kanıtları, kimlik doğrulama ve gizliliği koruyan protokolleri mümkün kılmakta ve blok zincirlerindeki doğrulanabilir hesaplamanın temelini oluşturmaktadır; olasılıksal olarak kontrol edilebilir kanıtlar ise birçok optimizasyon probleminin neden verimli bir şekilde yaklaştırılamadığını açıklayarak, yaklaştırma algoritmalarının nerede başarılı olup nerede olamayacağına rehberlik etmektedir.
Tarihçe
Etkileşimli ve sıfır bilgi kanıtları, 1980'lerin ortalarında Goldwasser, Micali ve Rackoff ile Babai tarafından tanıtılmıştır. Shamir, 1990'da IP'nin PSPACE'e eşit olduğunu kanıtlamış ve 1990'ların başlarında Arora ve diğerleri tarafından tamamlanan PCP teoremi, yaklaştırma çalışmalarında devrim yaratmıştır; rastgeleleştirilmiş polinom zamanın deterministik polinom zamana eşit olduğu yönündeki mevcut varsayım ise hala açık bir sorun olarak kalmaktadır.
Tartışmalar
- Rastgelelik, gerçek bir hesaplama gücü eklemekte midir?
- Birçok sonuç, makul zorluk varsayımları altında BPP'nin P'ye eşit olduğunu öne sürmektedir; bu da rastgeleliğin prensipte verimli algoritmalardan kaldırılabileceği anlamına gelmektedir. Bu rastgelelikten arındırmanın koşulsuz olarak geçerli olup olmadığı çözülememiş olup, rastgeleliğin gerçekte ne kadar temel olduğu sorusunu açık bırakmaktadır.
Öne çıkan isimler
- Shafi Goldwasser
- Silvio Micali
- László Babai
- Adi Shamir
İlgili konular
Temel eserler
- aroraBarak2009
- goldreich2008
Sıkça sorulan sorular
- Yazı tura atmak bir algoritmaya nasıl yardımcı olabilir?
- Rastgelelik, bir algoritmanın düşmanın tahmin edemeyeceği seçimler yaparak en kötü durum girdilerinden kaçınmasına olanak tanımakta, asal sayı testi gibi durumlarda genellikle daha basit veya daha hızlı prosedürler sağlamaktadır. Sınırlı hatalı BPP sınıfı, bu şekilde küçük, kontrol edilebilir bir hata olasılığıyla çözülebilen problemleri kapsamaktadır.
- Sıfır bilgi kanıtı nedir?
- Bu, bir doğrulayıcıyı bir ifadenin doğru olduğuna, doğruluğundan başka hiçbir şey, hatta neden doğru olduğuna dair bile bilgi vermeden ikna eden etkileşimli bir protokoldür. Bu tür kanıtlar, örneğin bir şifreyi veya sırrı açıklamadan bildiğinizi kanıtlamanıza olanak tanımakta ve modern kriptografik gizliliğin temelini oluşturmaktadır.