--- title: 'P–NP Sorusu' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/p-np-sorusu' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:30+00:00' license: 'CC BY-SA 4.0' --- # P–NP Sorusu Açık kalan sorunun ifadesi ve ölçülebilen tek şeyin ortaya konması: bilinen alt sınır 240, buluşma yordamı 1357, tam tarama 4321 adım harcıyor ve iki yordam 20 örneğin 20'sinde aynı yanıtı veriyor. Girdi boyu 24'te alt sınır 24, buluşma 8192, tam tarama 16.777.216 adım; açıklığın oranı 341,3'e karşı 699.050,7. Bir milyon adımlık bütçede tam tarama 19, buluşma 37 sayıya yetiyor. Soru açıktır ve bu derste hiçbir yön iddia edilmiyor. Dört sınıf adı ve aralarındaki bilinen ilişkiler kuruldu. Geriye en çok konuşulan, en az yanıtlanan soru kaldı: **doğrulanabilir olan her şey aynı zamanda çözülebilir mi.** Bu ders o soruyu ifade eder ve **ölçemeyeceğini ölçmeye çalışmaz.** Sorunun neden ölçülemediği ders boyunca sürekli görünür olacak. Ölçüm sonlu bir koşumdur ve sonlu bir koşum ancak "şu yordam şu kadar adım harcadı" der. Soru ise bütün yordamlar üzerine bir niceleyici taşır: "hiçbir yordam yok mu." Bu iki cümle arasındaki mesafe, bu dersin konusudur. Ölçülebilen tek şey **bilinen en iyi yordam ile bilinen alt sınır arasındaki farktır**. - **KS38.** Soru şu kapsama ilişkisidir: **P sınıfı NP sınıfının tamamına eşit midir.** P'nin NP'nin içinde olduğu `02`'de kuruldu; sorulan şey **ters yöndür**. - **KS39.** Soru **açıktır**. Bu derste hiçbir yön iddia edilmez, olası sayılmaz, "beklenir" denmez. - **KS40.** **Bilinen alt sınır**, hiçbir yordamın altına inemeyeceği gösterilmiş adım sayısıdır. Burada kullanılan alt sınır en zayıf olanıdır: girdiyi okumadan karar verilemeyeceği için **en az n adım**. - **KS41.** **Bilinen en iyi yordam**, bu derste kurulan yordamların en azını harcayanıdır. "Bilinen" sözcüğü bu kursun kapsamına göre okunur; kursun dışında daha iyisinin bulunup bulunmadığı burada ölçülmez. - **KS42.** İkinci yordam **buluşma yordamıdır**: girdi ikiye bölünür, ilk yarının bütün alt küme toplamları bir tabloya yazılır, ikinci yarı bu tabloya sorulur. - **KS43.** Buluşma yordamının doğruluğu varsayılmaz; her örnekte tam taramanın yanıtıyla karşılaştırılır. - **KS44.** Bir adım, tam tarama için **bir alt küme**, buluşma yordamı için **bir alt küme ya da bir sorgu**, alt sınır için **bir sayı okumasıdır**. - **KS45.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. İkinci süpürme girdi büyüklüğü üzerinedir. - **KS46.** Örnekler ortak tanımın üretecinden, tohum **20260218**. İkinci tohum yoktur. - **KS47.** Bir açıklığın daralması **yön göstergesi sayılmaz**. Daralma ölçülür, yorumlanmaz. ## Sorunun Kendisi İfade kısa ve tek anlamlıdır. P, girdi büyüklüğünün bir polinomuyla sınırlı adımda **çözülen** karar problemlerinin sınıfıdır. NP, "evet" yanıtı aynı sınırda **doğrulanan** problemlerin sınıfıdır. Her çözülen problem doğrulanabilir olduğuna göre P, NP'nin içindedir. Sorulan şey şudur: **NP'nin içinde, P'de olmayan bir problem var mı.** Sorunun bir yönü kurulmuştur ve gösterilmesi kolaydır. Öteki yön iki biçimde kapanabilirdi: ya NP-tam bir problem için polinom adımlı bir yordam bulunur ve iki sınıf çakışır, ya da öyle bir problem için polinom adımın yetmediği kanıtlanır ve ayrılırlar. **İkisi de yapılmamıştır** ve bu ders hangisinin olacağı hakkında hiçbir şey söylemez. Neden bir koşumun bu soruyu kapatamayacağı da açıktır. Bir yordamın 4096 adım harcaması, o problem için 4096 adımın gerektiğini göstermez; yalnız **o yordamın** o kadar harcadığını gösterir. Bir alt sınır kanıtı ise bütün yordamlar hakkında konuşur ve hiçbir koşum bütün yordamları tüketemez. Bu kursun aşırı iddia yasağı tam olarak bu boşluğu kapatmak içindir. ## Ölçülebilen Tek Şey Aşağıdaki blok üç sayıyı yan yana koyar: bilinen alt sınır, bu kursta kurulan en iyi yordamın adımı, ve tam taramanın adımı. Buluşma yordamının yanıtı her örnekte tam taramayla karşılaştırılır. ```python TOHUM = 20260218 def ornekler(tohum=TOHUM, n=12, sayi=20): d = tohum kume = [] for _ in range(sayi): sayilar = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 sayilar.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 kume.append({"sayilar": sayilar, "hedef": sum(sayilar) // 3 + d % 7}) return kume def tam_tarama(sayilar, hedef): """Bir adim = bir alt kume.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def bulusma(sayilar, hedef): """Girdi ikiye bolunur , her yarinin butun alt kume toplamlari cikarilir ve ikinci yaridan sorgulanir. Bir adim = bir alt kume ya da bir sorgu.""" n = len(sayilar) sol, sag = sayilar[: n // 2], sayilar[n // 2:] adim, tablo = 0, set() for maske in range(1 << len(sol)): adim += 1 tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1)) for maske in range(1 << len(sag)): adim += 1 t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1) if hedef - t in tablo: return True, adim return False, adim ORN = ornekler() uyan, tt, bt, asg = 0, 0, 0, 0 for o in ORN: y1, a1 = tam_tarama(o["sayilar"], o["hedef"]) y2, a2 = bulusma(o["sayilar"], o["hedef"]) uyan += y1 == y2 tt, bt, asg = tt + a1, bt + a2, asg + len(o["sayilar"]) print("20 ornek , n=12 | iki yordamin yaniti uyusan:", uyan, "/ 20") print(" bilinen alt sinir:", asg, "adim | bulusma yordami:", bt, "adim | tam tarama:", tt, "adim") print() print("butce tam tarama bulusma yordami") for b in (13, 100, 1000, 10000): c1 = sum(1 for o in ORN if tam_tarama(o["sayilar"], o["hedef"])[1] <= b) c2 = sum(1 for o in ORN if bulusma(o["sayilar"], o["hedef"])[1] <= b) print(f"{b:5d} {c1:10d} {c2:15d}") print() print(" n alt sinir bulusma tam tarama bulusma/alt sinir tarama/alt sinir") for n in (8, 12, 16, 20, 24): bul = (1 << (n - n // 2)) + (1 << (n // 2)) print(f"{n:2d} {n:9d} {bul:7d} {1 << n:10d} {bul / n:17.1f}" f" {(1 << n) / n:16.1f}") ``` ``` 20 ornek , n=12 | iki yordamin yaniti uyusan: 20 / 20 bilinen alt sinir: 240 adim | bulusma yordami: 1357 adim | tam tarama: 4321 adim butce tam tarama bulusma yordami 13 0 0 100 7 20 1000 19 20 10000 20 20 n alt sinir bulusma tam tarama bulusma/alt sinir tarama/alt sinir 8 8 32 256 4.0 32.0 12 12 128 4096 10.7 341.3 16 16 512 65536 32.0 4096.0 20 20 2048 1048576 102.4 52428.8 24 24 8192 16777216 341.3 699050.7 ``` ## Açıklığın Okunması Üç sayı yan yana: **alt sınır 240**, **buluşma 1357**, **tam tarama 4321**. İkinci yordam birincinin üçte birinden azını harcıyor ve 20 örneğin 20'sinde aynı yanıtı veriyor. Bu bir iyileşmedir, ölçüldü, ve gerçektir. Bütçe süpürmesi iyileşmenin nerede işe yaradığını gösteriyor. **Bütçe 100'de tam tarama 7 örnekte kalırken buluşma yordamı 20'de 20 veriyor.** Bütçe 1000'de tam tarama 19'a çıkıyor, 10.000'de ikisi de dolu. Yani iyileşmenin görünür olduğu bir bütçe aralığı var ve o aralığın dışında iki yordam ayırt edilemiyor. Girdi boyu tablosu asıl soruyu yanıtlıyor: **açıklık kapanıyor mu.** Buluşma sütunu 32, 128, 512, 2048, 8192; her satırda dörde katlanıyor. Tam tarama sütunu 256'dan 16.777.216'ya, her satırda on altıya katlanarak gidiyor. Alt sınıra oranlar ise 4,0'dan **341,3**'e ve 32,0'dan **699.050,7**'ye çıkıyor. Okunması gereken şey iki sütunun **ikisinin de büyümesidir**. İyileşme oranı azaltmadı; artış hızını azalttı. Yirmi dört sayıda buluşma yordamı tam taramadan 2048 kat ucuz, ama alt sınırdan hâlâ 341 kat pahalı. **Açıklık daraldı, kapanmadı** ve bu tabloda kapanacağına dair hiçbir işaret yoktur — kapanmayacağına dair de yoktur. ## İyileşme İki Yönde de Var Mı Evet kümesindeki 3,18 katlık kazanç kısmen erken durmadan geliyor olabilir: tam tarama uyan alt kümeyi bulunca duruyor ve bu, ona haksız bir avantaj değil, gerçek bir indirim sağlıyor. Kazancın yapıdan mı yoksa erken durmadan mı geldiği, erken durmanın hiç olmadığı bir kümede ölçülür. `04`'ün yapısız hayır örnekleri tam olarak böyledir. ```python TOHUM = 20260218 def ornekler(tohum=TOHUM, n=12, sayi=20): d = tohum kume = [] for _ in range(sayi): sayilar = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 sayilar.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 kume.append({"sayilar": sayilar, "hedef": sum(sayilar) // 3 + d % 7}) return kume def ulasilmayan(sayilar): """Kurulum adimi: erisilmeyen bir hedef secilir , yanit kesin 'hayir'.""" ulasilan = {0} for x in sayilar: ulasilan |= {u + x for u in ulasilan} return min((t for t in range(1, sum(sayilar)) if t not in ulasilan), key=lambda t: abs(t - sum(sayilar) // 3)) def tam_tarama(sayilar, hedef): adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def bulusma(sayilar, hedef): n = len(sayilar) sol, sag = sayilar[: n // 2], sayilar[n // 2:] adim, tablo = 0, set() for maske in range(1 << len(sol)): adim += 1 tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1)) for maske in range(1 << len(sag)): adim += 1 t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1) if hedef - t in tablo: return True, adim return False, adim ORN = ornekler() EVET = [(o["sayilar"], o["hedef"]) for o in ORN] HAYIR = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ORN] print("kume uyusan tam tarama bulusma oran") for ad, kume in (("evet ", EVET), ("hayir", HAYIR)): uyan = tt = bt = 0 for s, h in kume: y1, a1 = tam_tarama(s, h) y2, a2 = bulusma(s, h) uyan += y1 == y2 tt, bt = tt + a1, bt + a2 print(f"{ad} {uyan:6d} {tt:10d} {bt:7d} {round(tt / bt, 2):5}") ``` ``` kume uyusan tam tarama bulusma oran evet 20 4321 1357 3.18 hayir 20 81920 2560 32.0 ``` Hayır kümesinde iki yordam da erken duramıyor, yani ikisi de işlerinin tamamını yapıyor. Tam tarama **81.920**, buluşma **2560** adım harcıyor ve oran **32,0**. Bu, evet kümesindeki 3,18'in on katıdır. Sonuç şudur: **kazancın kaynağı erken durma değil, yordamın yapısıdır**; evet kümesindeki oranın düşük görünmesi, tam taramanın oradan bir indirim almasındandır. Bu ayrım açık soruyla ilgilidir. Bir iyileşmenin gerçekten yapısal olup olmadığı, ancak indirimsiz bir kümede ölçülerek görülür. Buna karşın **32,0 oranı da bir yön göstermez**: sabit bir çarpanla bölünen bir üstel, hâlâ bir üsteldir ve tablo bunu 24 sayıda 341 katlık uzaklıkla zaten göstermişti. ## Bütçe Sabitken Ne Kadar İleri Gidilir İyileşmenin mühendislikteki karşılığı orandan çok **erişilen girdi büyüklüğüdur**. Bir adım bütçesi sabitlenip her yordamın o bütçede en çok kaç sayı işleyebildiği hesaplanabilir. Aşağıdaki tablo üçüncü bir sütun daha taşır ve o sütun **varsayımsaldır**: karesel adımlı bir yordam bulunsaydı ne olurdu. Böyle bir yordamın var olduğu iddia edilmiyor; sütun yalnız sorunun neyi değiştireceğini gösteriyor. ```python def en_buyuk_n(butce, maliyet, ust=200000): """Butce icinde kalan en buyuk girdi buyuklugu.""" en = 0 for n in range(1, ust + 1): if maliyet(n) <= butce: en = n return en def tarama(n): return 1 << n def bulusma(n): return (1 << (n - n // 2)) + (1 << (n // 2)) def karesel(n): return n * n print("adim butcesi tam tarama bulusma varsayimsal n^2") for b in (10 ** 4, 10 ** 6, 10 ** 8, 10 ** 10): print(f"{b:14d} {en_buyuk_n(b, tarama):10d} {en_buyuk_n(b, bulusma):7d}" f" {en_buyuk_n(b, karesel):15d}") ``` ``` adim butcesi tam tarama bulusma varsayimsal n^2 10000 13 24 100 1000000 19 37 1000 100000000 26 50 10000 10000000000 33 64 100000 ``` Bütçe on bin katına çıkarıldığında tam taramanın eriştiği girdi büyüklüğü 13'ten 33'e çıkıyor: bütçe on binlerce kat büyüyor, girdi büyüklüğü **yirmi sayı** kazanıyor. Buluşma yordamı aynı bütçelerde 24'ten 64'e gidiyor, yani her bütçede tam taramanın **yaklaşık iki katı** girdiye yetiyor. Bu gerçek ve ölçülmüş bir kazançtır. Üçüncü sütun farkın niteliğini gösteriyor. Varsayımsal karesel yordam aynı bütçelerde 100'den **100.000**'e çıkıyor. İlk iki sütun bütçeyi büyüterek birkaç sayı kazanıyor, üçüncüsü büyüklük düzeyi kazanıyor. P–NP sorusunun mühendislikteki karşılığı bu iki davranış arasındaki farktır: birinci ve ikinci sütun aynı ailedendir, üçüncüsü başka bir ailedendir, ve alt küme toplamı probleminin hangi ailede olduğu **bilinmiyor**. ## Bu Dersin Söylemediği Yukarıdaki hiçbir sayı bir yön göstermez ve gösterecek biçimde okunmamalıdır. Buluşma yordamının tam taramayı 2048 kat geçmesi, daha iyisinin bulunacağını **düşündürmez**; buluşma yordamının alt sınırdan 341 kat uzak kalması da bulunmayacağını düşündürmez. Ölçüm bu iki cümlenin hiçbirini destekleyecek türden bir şey değildir. Söylenebilecek olan tam olarak şudur. Bu derste kurulan en iyi yordam 12 sayıda 1357 adım harcadı; bilinen alt sınır 240 adımdı; aradaki oran girdi büyüklüğü 24'te 341,3'e çıktı. Bu cümle ölçülmüştür ve bütçesiyle birlikte yazılmıştır. "Alt küme toplamı polinom zamanda çözülemez" cümlesi ise ölçülmemiştir, bu kursta kanıtlanmamıştır ve **kimse tarafından kanıtlanmamıştır**; yazılırsa kurala aykırıdır. Aynı katılık ters yön için de geçerlidir. "Bir gün polinom bir yordam bulunacak" cümlesi de ölçülmüş değildir. Açık bir soru hakkında yazılabilecek tek dürüst cümle, sorunun açık olduğunu söyleyen cümledir. ## Mühendislikte Karşılığı Sorunun açık kalması bir mühendisi işsiz bırakmaz; tersine, ne yapılacağını netleştirir. Bir problemin NP-tam bir probleme indirgendiği biliniyorsa, o probleme genel ve ucuz bir çözüm aramak, **çözülmemiş bir kuram sorusunu çözmeye çalışmakla aynı şeydir**. Bu, yapılamaz demek değildir; yapılan işin ne olduğunu doğru adlandırmaktır. Pratikte üç yol kalır ve üçü de bu kursta ölçüldü ya da ölçülecek. Birincisi girdiyi küçük tutmaktır: bütçe tablosu 12 sayıda hangi yordamın yettiğini gösterdi. İkincisi yordamı iyileştirmektir: buluşma yordamı erişilen girdi büyüklüğünu iki katına çıkardı. Üçüncüsü kesin çözümden vazgeçmektir, ve bu sonraki dersin konusudur. ## Özet - P–NP sorusu, NP sınıfının içinde P'de olmayan bir problem bulunup bulunmadığını sorar ve **açıktır**; bu ders hiçbir yön iddia etmez. - Sonlu bir koşum soruyu kapatamaz, çünkü bir yordamın adımını ölçer, bütün yordamlar hakkında konuşamaz. - Yirmi örnekte bilinen alt sınır 240, buluşma yordamı 1357, tam tarama 4321 adım; iki yordam 20 örneğin 20'sinde aynı yanıtı veriyor. - Girdi boyu 8'den 24'e çıkarken buluşma 32'den 8192'ye, tam tarama 256'dan 16.777.216'ya gidiyor; alt sınıra oran 4,0'dan 341,3'e ve 32,0'dan 699.050,7'ye çıkıyor. Açıklık daraldı, kapanmadı. - Bir milyon adımlık bütçede tam tarama 19, buluşma 37 sayıya yetiyor; varsayımsal karesel bir yordam 1000 sayıya yeterdi. - Açık bir soru hakkında yazılabilecek tek dürüst cümle, ölçülmüş açıklığı bütçesiyle birlikte bildiren ve sorunun açık olduğunu söyleyen cümledir. ## Sonraki Adım Bu ders üçüncü yolu açıkta bıraktı: kesin çözümden vazgeçmek. Sonraki ders bunun bedelini sayar. Yaklaşık bir çözüm kaç örnekte kesin sonucu buluyor, bulamadığında ne kadar uzağa düşüyor, ve yaklaşık yordama verilen bütçe büyütüldüğünde kayıp gerçekten kapanıyor mu. Kursun ve M01 müfredatının son dersi bu soruyla biter.