Klasik Karmaşıklık Sınıfları P ve NP

Kuantum algoritmaların hızını söyleyebilmek için önce klasik hesaplamanın hızını ölçmeyi öğrenmek gerekir. Bu derste bilgisayar biliminin en temel ayırımını, yani P ve NP sınıflarını sıfırdan anlatacağız: hangi problemler pratikte çözülebilir, hangileri yalnızca pratikte doğrulanabilir? Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; önceki ünitelerdeki Shor Algoritmasının bu tabloda nereye oturduğunu son bölümde göreceksin.

P Sınıfı: Polinom Zamanında Çözülebilen Problemler

Karmaşıklık teorisi çoğunlukla karar problemleriyle, cevabı evet ya da hayır olan sorularla ilgilenir. Girdinin boyutuna n deriz; ölçüt, en kötü durumdaki adım sayısının n ile nasıl büyüdüğüdür. n = 100 için tipik büyüme sınıfları:

• O(n): listeyi taramak → ~100 adım
• O(n log n): sıralama → ~664 adım
• O(n²): tüm çiftlere bakmak → 10.000 adım
• O(2ⁿ): tüm alt kümeleri denemek → 2¹⁰⁰ ≈ 1,27 × 10³⁰ adım

Fark ölçekle patlar: girdiyi 10 kat büyütmek n²'lik işi 100 kat, 2ⁿ'lik işi ~1024 kat büyütür. Teorinin “iyi” dediği büyüme polinom zamandır: adım sayısı n, n², … nᵏ gibi n'in çokterimlisidir. Üstel tarafta n = 60 bile 2⁶⁰ ≈ 1,15 × 10¹⁸ adımdır — evler sürer.

P (polinom zaman), her adımda tek kesin seçim yapan klasik — deterministik — bir makinede, girdi boyutunun sabit bir polinomu kadar adımda çözülebilen karar problemlerinin sınıfıdır. Örnekler:

• Listeyi sıralamak; sıralı listede arama
• En kısa yol (Dijkstra); en büyük ortak bölen (Öklid)
• Matris çarpımı; lineer denklem sistemleri
• Bir sayının asal olup olmadığı (2002'de AKS ile P'de olduğu kanıtlandı)

İnce ayrıntı: asallığını söylemek P'dedir; çarpanlarını bulmak P'de bilinmez — karar kolayken yapı çıkarma zor kalabilir.

NP Sınıfı: Doğrulanması Hızlı, Çözümü Belki Yavaş

Bazı problemlerde çözümü bulmak zordur ama bir aday çözüm — buna kanıt denir — verilince doğruluğunu hızlıca denetleyebilirsin: Sudoku'da çözmek saatler, denetlemek dakikalar sürer. NP (nondeterministic polynomial), kanıdı polinom zamanda doğrulanabilen karar problemlerinin sınıfıdır. “Belirlenimsiz” sözü bir düşünce deneyidir: doğru kanıtı şanslıca tahmin eden bir makine NP'deki her problemi polinom zamanda çözerdi.

Adım adım bir örnek: {3, 34, 4, 12, 5, 2} sayılarından toplamı 9 olan alt küme var mı? (alt küme toplamı)

1. Kanıtsız çözüm: 2⁶ = 64 alt kümeyi dene — küçükte kolay; 60 sayıda 2⁶⁰ ≈ 1,15 × 10¹⁸ deneme gerekir.
2. Kanıt: biri sana {4, 5} alt kümesini işaret etsin.
3. Doğrulama: 4 ve 5 listede var, 4 + 5 = 9; birkaç işlemde evet kesinleşir.
4. “Çözüm yok” demek ise tüm 2ⁿ alt kümeyi elemek demektir — kolaylık tek yönlüdür.

İki gözlem tanımı tamamlar. Birincisi P ⊆ NP: hızlı çözülen her problem hızlıca da doğrulanabilir. İkincisi, NP “non-polynomial” demek değildir: polinom algoritması bilinen binlerce problem NP'dedir, P dâhil.

P = NP Sorusu ve NP-Tam Problemler

Doğrulaması hızlı her problem hızlı da çözülebilir mi? “P = NP mi?” sorusu alanın en ünlü açık problemi ve Clay'in Milyon Dolarlık Problemler'indendir. Cook–Levin sonucu (1971/1973) şunu koyar: SAT — bir mantık formülünü doğruyan değer ataması var mı? — NP'deki her problemin ona azaltılabildiği bir problemdir; SAT'i hızlı çözebilseydin tüm NP'yi onun üzerinden çözebilirdin.

Bu tür problemlere NP-tam denir: NP'dedirler ve NP'nin tamamı onlara polinom zamanda azaltılabilir. Sonuç çarpıcıdır: tek bir NP-tam probleme polinom algoritma bulmak, P = NP demektir. SAT, Hamilton döngüsü, alt küme toplamı ve gezgin satıcının karar hâli NP-tamdır. Katmanlar:

• P: hızlı çözülür ve doğrulanır — sıralama, en kısa yol
• NP: hızlı doğrulanır — SAT, alt küme toplamı
• NP-tam: NP'nin en zorları; biri çözülürse hepsi çözülür — SAT, Hamilton döngüsü
• NP-zor: en az NP-tam kadar zor, NP'de olmak şart değil — gezgin satıcı optimizasyonu

Pratikte kriptografi “doğrulamak kolay, çözmek zor” varsayımına yaslanır; P = NP çıkarsa tek yönlü fonksiyonlar çöker. Bu yüzden araştırmacıların çoğu P ≠ NP bekler — ama kanıt yoktur.

Kuantum Hesaplama Bu Resmin Neresinde?

Soru, kuantumda polinom zamanda çözülebilen problemlerin sınıfı olan BQP'nin P ve NP ile nerede durduğudur. İki veri: Shor Algoritması çarpanlara ayırmayı polinom zamanda çözer; Grover aramayı yaklaşık √N sorguya indirir (tazelemek için Kuantum Hesaplama 101). Dikkat: çarpanlara ayırma NP-tam değildir, NP ∩ coNP içindedir; Shor “NP'yi fethetti” demek değildir.

Grover'ı NP-tam bir probleme uygulasan 2ⁿ'lik uzayı O(2^(n/2))'ye indirirsin: karesel kazanç güzeldir ama üstel üstel olarak kalır. Genel kabul P ⊆ BPP ⊆ BQP zinciri ve BQP'nin NP-tam içermediğidir; hızlanma Shor'daki gibi gizli örüntülerden (periyodiklik) doğar. Komşu dersler:

• Olasılıksal Karmaşıklık BPP — zincirdeki klasik olasılıksal sınıf
• Kuantum Karmaşıklık Sınıfı BQP — tanım ve P, NP ile ilişkisi
• Kuantum Hızlanması — kuantumun gerçekten hızlandığı problem türleri
• Oracle Modelleri — ayrım kanıtlarının neden zor olduğu
• Sorgu Karmaşıklığı — Grover'ın √N sınırının ölçüldüğü eksen

Sık Yapılan Hatalar

• “NP = non-polynomial” okumak — NP “nondeterministic polynomial” demektir; P zaten NP içindedir.
• “NP = zor problemler” sanmak — NP'de kolay (P) üyeler de vardır.
• “Shor NP-tam bir problemi çözdü” sanmak — çarpanlara ayırma NP-tam değildir.
• “Kuantum her şeyi paralel dener” sanmak — ölçüm tek sonuç verir; Grover'ın kazancı yalnızca kareseldir.

Özet: P çözmenin, NP doğrulamanın, NP-tam ise birbirine bağlı en zor problemlerin adresidir. Grover karesel hızlanma, Shor çarpanlara ayırmada polinom zaman verir; ama NP-tam için üsteli kıran bilinen bir kuantum yöntem yoktur.

İçindekiler için Konu Anlatımı sayfasına bak; serinin ilerleyen ünitelerinde ilk durak Bit Flip ve Phase Flip Hataları olacak.

Kaynaklar ve İleri Okuma

P versus NP problem — Wikipedia — tanım, tarihçe ve bilinen sonuçlar.

P (complexity) — Wikipedia — P sınıfının tanımı ve örnek problemleri.

NP-completeness — Wikipedia — NP-tamlık, azaltma ve klasik NP-tam problem listesi.

PHYS771 Lecture 6: P, NP, and Friends — Scott Aaronson — sezgisel ama titiz bir ders notu.

BQP — Wikipedia — kuantum sınıfı BQP'nin tanımı ve P, NP ile karşılaştırması.