Olasılıksal Karmaşıklık BPP

Pek çok hızlı algoritmanın arkasında öngörülebilir bir makine değil, yazı tura atan bir makine vardır. Bu derste rastgeleliğe izin veren polinom zamanlı hesaplamanın standart sınıfı BPP’yi (Bounded-error Probabilistic Polynomial time) tanımlayacak, hatayı çoğunluk oyuyla nasıl üstel biçimde küçülttüğümüzü göreceğiz ve sınıfı P, NP ile kuantum kardeşi BQP’nin yanındaki yerine oturtacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; P ve NP’yi henüz görmediysen önce Klasik Karmaşıklık Sınıfları P ve NP dersine göz atman iyi olur.

Rastgelelikten BPP’ye: Sınıfın Tanımı

Deterministik makine girdide her zaman aynı yolu izler; olasıtsal (rastgeleleştirilmiş) makine ise hesap sırasında madeni para atabilir. Bir karar problemi BPP’dedir eğer makine her girdide polinom zamanda duruyor, cevabı “evet” olan girdilerde en az 2/3 olasılıkla evet, cevabı “hayır” olanlarda en az 2/3 olasılıkla hayır diyorsa. Hata iki yönde de olabilir ama 1/2’den kesin biçimde aşağıda kalmalıdır — “bounded error” (sınırlı hata) bunu söyler.

2/3 sayısı önemsizdir: 1/2’nin üstündeki her sabit hata büyütmeyle aynı sınıfı verir; 2/3 yalnızca gelenektir. Sınır tam 1/2 olsaydı makine saf para atışından ayırt edilemezdi. BPP iki taraflı hataya izin verir; tek yönlü kardeşleri de tanımlıdır:

• RP: tek taraflı hata; “hayır” cevabı kesindir, yalnızca gerçekten evet olan girdilerde 1/2’ye dek yanılabilir (Monte Carlo tarzı).
• coRP: RP’nin aynadaki hâli; bu kez “evet” cevabı kesindir.
• ZPP: sıfır hata; cevap her zaman doğrudur, yalnızca çalışma süresi beklenen değeriyle polinomdur (Las Vegas tarzı).

Hata Büyütme: Çoğunluk Oyuyla 2⁻ᵏ’ye İnmek

BPP algoritmasını k kez bağımsız çalıştırıp çoğunluk oyu alırsan hata hızla erir. Tek çalıştırmanın hata olasılığı 1/3 olsun, k = 3: çoğunluğun yanması için en az iki çalıştırma gerektiğinden toplam hata = C(3,2) × (1/3)² × (2/3) + (1/3)³ = 6/27 + 1/27 = 7/27 ≈ 0,26. Sonuç 1/3’ün altında; tekrar işe yarıyor.

Genel adım Chernoff sınırıyla verilir: hata olasılığı 1/3 olan k bağımsız denemenin çoğunluğunun yanılma olasılığı en fazla e^(−k/18)’dir. Yani k’yı lineer büyütmek hatayı üstel kırpar: k = 40 için hata ≈ %11; 10⁻¹² için k ≈ 500 gerekir. Maliyet yalnızca k katı zamandır, polinom kalır.

Somut Örnek: Miller–Rabin Asallık Testi

Soru: n tek sayısı asal mı? Ardışık bölme n’in basamak sayısına üstel büyür. Miller–Rabin n−1 = 2^s·d (d tek) yazar ve rastgele bir a seçer: a^d ≡ ±1 (mod n) ya da kare zinciri −1’e ulaşırsa taban geçer; aksi hâlde n kesinlikle bileşiktir. Tabanlar geçilirse n “büyük olasılıkla asal”dır; test “bileşik” derken asla şaşmaz.

Örneği n = 91 = 7 × 13 için izleyelim: 90 = 2 × 45, yani s = 1, d = 45. a = 2: 2^45 ≡ 57 ∉ {1, 90} (mod 91); kare hakkı kalmadığından taban n’i ele verir. a = 3 Fermat testini kandırır (3^90 ≡ 1) ama güçlü test yakalar: 3^45 ≡ 27 ∉ {1, 90} ve 27² ≡ 1’e −1’den geçmeden ulaşır. a = 10 ise gerçek bir güçlü yalancı tanıktır: 10³ ≡ −1 (mod 91); 10^45 ≡ −1, taban geçer. Bileşik sayılarda rastgele a’ların en fazla 1/4’ü güçlü yalancıdır: k tabanla hata 4⁻ᵏ’nın altına iner; 5 deneme binde birin altına indirir.

Bu örnek iki yüzü de gösterir: 2002’de AKS algoritması asallığın deterministik polinom zamanda çözülebileceğini kanıtladı — yine de pratikte kripto kütüphaneleri hâlâ onu kullanır. Rastgeleliğin gerçek iş yaptığı örnek polinom kimlik testidir: iki cebirsel ifadenin eşitliği rastgele bir noktada değerlendirilerek Schwartz–Zippel önsavıyla yüksek olasılıkla doğrulanır; bunun deterministik hızlı yöntemi hâlâ açık problemdir.

BPP’nin Yeri: P, NP ve BQP ile İlişkisi

Bilinen kapsanmalar: P ⊆ BPP ⊆ PSPACE. İlk ok açıktır: hiç para atmayan makine BPP’nin özel hâlidir. İkincisi: tüm para-atış dizileri polinom bellekte sayılabilir. Adleman’ın 1978 teoremi bir adım ileri gider (BPP ⊆ P/poly): her girdi uzunluğu için, o uzunluktaki tüm girdileri doğru cevaplayan tek bir sabit atış dizisi vardır — yani her seviye polinom büyüklüklü devreyle çözülür. Buna karşılık BPP’nin NP’nin içinde olup olmadığı açık bir sorudur; “BPP ⊆ NP’dir” demek yaygın bir yanılgıdır.

Büyük açık soru: BPP = P mi? Çoğu araştırmacı evet der; Impagliazzo–Wigderson (1997), bir problemin üstel büyüklüklü devreler gerektirmesi koşuluyla P = BPP olacağını gösterdi. Özet: rastgelelik hesaplamaya yeni güç değil, zarafet katar — hız ve sadelik sağlar, polinom zaman sınırını değiştirmez.

Kuantum karşılığı BQP’dir: aynı “polinom zaman + sınırlı hata” kalıbı, ama yazı tura yerine kübit, süperpozisyon ve dolanıklık. BPP ⊆ BQP kesindir, çünkü para atışı yarım–yarım süperpozisyon ölçülerek kuantumda taklit edilir. Ters yönü bilinmez: çarpanlara ayırma Shor Algoritması ile BQP’dedir ama BPP’de olduğu gösterilememiştir. Aramada klasik rastgele yöntem N adaya Θ(N) sorgu atarken Grover √N ile yeter; kesin ölçü için Sorgu Karmaşıklığı ve Oracle Modelleri derslerine bak. BQP’nin tanımı için Kuantum Karmaşıklık Sınıfı BQP, genel tablo için Kuantum Hızlanması dersini oku.

Sık Yapılan Hatalar ve Yanılgılar

• “BPP yanlış cevap verebilir, güvenilmez.” k = 40 tekrarla hata ≈ %11; 10⁻¹² için k ≈ 500 gerekir — kozmik bir ışığın işlemcide bit çevirmesinden küçük.
• “2/3 sihirli bir sabittir.” Değil: 1/2’nin üstündeki her sabit, hatta 1/2 + 1/p(n) başarı olasılığı bile büyütmeyle aynı sınıfı verir.
• “BPP ⊆ NP’dir.” Bilinmiyor. Bilinenler: P ⊆ BPP ⊆ PSPACE, BPP ⊆ P/poly ve BPP ⊆ PH; BPP–NP ilişkisi açık sorudur.
• “BQP ile BPP aynı şeyin iki adıdır.” BPP klasik rastgelelik, BQP kuantum süperpozisyon kullanır; süperpozisyonu yazı-tura dizisiyle taklit etmek genelde üstel sayıda deneme gerektirir.
• “Rastgelelik her zaman güç katar.” Miller–Rabin’e karşın AKS vardır. İnanılan tablo: BPP = P; rastgelelik hız ve sadelik sağlar, sınıf değiştirmez.

Bu ders ünitenin ikinci halkasıydı: klasik dünyada rastgeleliğin gücü ve sınırı netleşti; bir sonraki derste kuantum karşılığı BQP’yi derinlemesine işleyeceğiz. Temeller için Kuantum Hesaplama 101, tüm derslerin içindekiler için Konu Anlatımı sayfasına bakabilirsin.

Kaynaklar ve İleri Okuma

BPP (complexity) — English Wikipedia — sınıfın tanımı, hata büyütme ve bilinen kapsanmalar.

Miller–Rabin primality test — English Wikipedia — test adımları ve yalancı tanık oranı 1/4 sınırı.

AKS primality test — English Wikipedia — asallığın 2002’de deterministik polinom zamanda çözüldüğü sonucu.

Complexity Zoo: B — BPP, RP, ZPP ve BQP dâhil karmaşıklık sınıflarının kısa ve güncel tanımları.