--- title: 'NP Sınıfı' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/np-sinifi' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:28+00:00' license: 'CC BY-SA 4.0' --- # NP Sınıfı Doğrulanabilirlik ve sertifika kavramının adım sayısıyla kurulması: 20 örnekte çözme 4321, sertifika doğrulama 101 adım harcıyor ve oran 42,8. Adım bütçesi 13'te sertifikayla 20 örneğin 20'si karara bağlanırken çözerek hiçbiri bağlanmıyor. Girdi boyu 24'te çözmenin en kötüsü 16.777.216, doğrulama 25 adım. Bir indisi düşürülmüş sertifika 20 örneğin 20'sinde reddediliyor. Sertifika teriminin Kriptografi müfredatındaki sayısal sertifika duyusundan farkı ayrıca yazılıyor. Önceki ders alt küme toplamı problemini 12 sayıda 1047 adıma kadar taradı ve tarama bitince elde bir şey daha kaldı: hedefe toplanan alt kümenin **kendisi**. O alt küme bir kez yazıldıktan sonra doğruluğunu görmek için taramayı yeniden yapmak gerekmiyor; birkaç toplama yetiyor. Bu ders o gözlemi ölçüye çevirir. Ölçülen fark bir hız farkı değil, **iki ayrı soruya verilen iki ayrı bedeldir**. Birinci soru: hedefe toplanan bir alt küme var mı. İkinci soru: **verilen** şu alt küme hedefe toplanıyor mu. İkinci soruyu yanıtlayan yordam hiçbir arama yapmaz; yalnız bakar. - **KS11.** **Sertifika**, bir "evet" yanıtını doğrulanabilir kılan tanıktır. Burada bir indis listesidir: hangi sayıların alındığı. - **KS12.** **Hakem**, sertifikayı alıp "evet" yanıtını sınayan yordamdır. Hakem **arama yapmaz**; bu, bu dersin en katı kısıtıdır. Arama yapan bir hakem çözücüdür. - **KS13.** Bir adım, hakem için **bir indis okumasıdır**; son karşılaştırma da bir adım sayılır. Çözücü için bir adım, **bir alt kümedir**. - **KS14.** Sertifikanın **uzunluğu** ölçülür. Girdi boyuyla orantılı kalmayan bir sertifika, doğrulamayı ucuzlatmaz. - **KS15.** Hakem yalnız kabul etmekle değil, **reddetmekle** de sınanır: bozulmuş bir sertifika verildiğinde ne dediği sayılır. - **KS16.** Sertifika "hayır" yanıtı için tanımlı değildir. Bu dersin ölçtüğü tek yön **evet** yönüdür; öteki yön `04`'e aittir. - **KS17.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. - **KS18.** Örnekler ortak tanımın üretecinden, tohum **20260218**, 20 örnek, örnek başına 12 sayı. İkinci tohum yoktur. - **KS19.** Bir problemin NP sınıfına ait olup olmadığı **ölçülmez**. Ölçülen şey, belirli bir hakemin belirli bir sertifikayı kaç adımda sınadığıdır. ## Sertifika Hangi Anlamda Kullanılıyor Aynı sözcük M24 Kriptografi müfredatında da geçer ve orada başka bir şeyi adlandırır. Fark tek bir cümleyle yazılır: **orada sertifika, bir kimliği bir açık anahtara bağlayan imzalı bir belgedir; burada sertifika, bir karar probleminin "evet" yanıtını kısa adımda sınanabilir kılan tanıktır.** İkisinin ortak yanı yalnız "kendisi üretilmeden de doğrulanabilir" olmalarıdır; ötesinde ilişkileri yoktur ve aynı cümlede kullanılmazlar. **NP**, bir karar problemi sınıfıdır: "evet" yanıtı, girdi büyüklüğünün bir polinomu uzunluğunda bir sertifikayla ve yine polinom adımda **doğrulanabilen** problemler. Tanımda "çözmek" geçmez. Bu yüzden NP, "polinom zamanda çözülemeyen" demek **değildir**; adın açılımı da bunu söylemez. P sınıfındaki her problem NP sınıfındadır: bir problemi polinom adımda çözebilen bir yordam varsa, hakem sertifikayı hiç okumadan problemi baştan çözer ve yanıtı verir. Ters yönün doğru olup olmadığı bu kursun `05` dersinin konusudur ve **açıktır**. ## Çözmek ile Doğrulamak Aşağıdaki blok her örnekte önce çözücüyü koşturur, çözücünün ürettiği sertifikayı alır ve hakeme verir. Sonra aynı sertifikanın bir indisi düşürülüp hakeme yeniden verilir. ```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 cozucu(sayilar, hedef): """Butun alt kumeler taranir. Doner: (var_mi, adim, sertifika).""" 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, [i for i in range(n) if maske >> i & 1] return False, adim, None def hakem(sayilar, hedef, sertifika): """Verilen sertifikayi dogrular; hicbir arama yapmaz. Bir adim = bir indis okumasi.""" adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 KAYIT = [] for o in ornekler(): var, adim, sert = cozucu(o["sayilar"], o["hedef"]) ok, da = hakem(o["sayilar"], o["hedef"], sert) KAYIT.append({"ornek": o, "var": var, "cozme": adim, "sertifika": sert, "dogrulama": da, "gecerli": ok}) tc = sum(k["cozme"] for k in KAYIT) td = sum(k["dogrulama"] for k in KAYIT) print("20 ornek , n=12 | evet yaniti:", sum(1 for k in KAYIT if k["var"]), "/ 20") print(" hakem sertifikayi onayladi:", sum(1 for k in KAYIT if k["gecerli"]), "/ 20") print(" cozme adimi:", tc, "| dogrulama adimi:", td, "| oran:", round(tc / td, 1)) print(" en uzun sertifika:", max(len(k["sertifika"]) for k in KAYIT), "indis") print() print("butce cozerek kurulan sertifikayla kurulan") for b in (13, 100, 1000, 10000): c1 = sum(1 for k in KAYIT if k["cozme"] <= b) c2 = sum(1 for k in KAYIT if k["dogrulama"] <= b) print(f"{b:5d} {c1:14d} {c2:21d}") print() ret, ra = 0, 0 for k in KAYIT: s = k["sertifika"] kirpik = s[:-1] if len(s) > 1 else s + [0] ok, a = hakem(k["ornek"]["sayilar"], k["ornek"]["hedef"], kirpik) ra += a ret += not ok print("bir indisi dusurulmus sertifika | reddedilen:", ret, "/ 20", "| toplam adim:", ra) ``` ``` 20 ornek , n=12 | evet yaniti: 20 / 20 hakem sertifikayi onayladi: 20 / 20 cozme adimi: 4321 | dogrulama adimi: 101 | oran: 42.8 en uzun sertifika: 5 indis butce cozerek kurulan sertifikayla kurulan 13 0 20 100 7 20 1000 19 20 10000 20 20 bir indisi dusurulmus sertifika | reddedilen: 20 / 20 | toplam adim: 81 ``` ## Üç Sayının Okunması **Bütçe 13**: sertifikayla 20 örneğin 20'si karara bağlanıyor, çözerek **hiçbiri**. Bütçe 100'de çözme 7'ye, 1000'de 19'a, 10.000'de 20'ye çıkıyor. Sertifika sütunu ise **hiç değişmiyor**: en küçük bütçede zaten doldu ve büyütmek eklenecek bir şey bulamadı. Bu kursun ikinci iddiasının en temiz görünümü budur — bütçeyi büyütmek bir sütunda her şeyi, ötekinde hiçbir şeyi değiştiriyor. Toplamlar aynı şeyi söylüyor: çözme **4321**, doğrulama **101** adım, oran **42,8**. Sertifika uzunluğu en çok **5 indis**; girdide 12 sayı var, yani sertifika girdiden kısa. Uzunluğun ölçülmesi biçimsel bir titizlik değil: hakemin adım sayısı sertifikanın uzunluğuna bağlıdır, ve girdiden uzun bir sertifikaya izin verilirse doğrulamanın ucuzluğu kendiliğinden yok olur. Dördüncü sayı hakemin ciddiyetini gösteriyor. Sertifikadan bir indis düşürüldüğünde 20 örneğin **20'sinde** hakem reddediyor ve bunu toplam **81 adımda** yapıyor. Reddetmek, kabul etmekten daha ucuza gelmiyor ama daha pahalıya da gelmiyor; hakem her iki durumda da yalnız bakıyor. Bu ölçüm olmadan "doğrulama ucuzdur" cümlesi eksik kalırdı: her sertifikayı onaylayan bir yordam da ucuzdur ve hiçbir işe yaramaz. ## Sertifikanın Kısalığı Neden Tanımın Parçası NP tanımı sertifikanın **polinom uzunlukta** olmasını ister. Bu koşul kaldırılırsa tanım boşalır, ve bu ölçülebilir. Aşağıdaki blok aynı problem için üç ayrı sertifika tasarımını yan yana koyar: indis listesi, yalnızca "evet" sözcüğü, ve bütün alt küme toplamlarının listesi. ```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 kisa_sertifika(sayilar, hedef): """Indis listesi. Uzunluk en cok n.""" n = len(sayilar) for maske in range(1 << n): if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return [i for i in range(n) if maske >> i & 1] return [] def kisa_hakem(sayilar, hedef, sertifika): adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 def bos_hakem(sayilar, hedef, sertifika): """Sertifika yalnizca 'evet' sozcugu; hakem aramak zorunda kalir.""" 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 uzun_sertifika(sayilar, hedef): """Butun alt kume toplamlari sirayla yazilir. Uzunluk 2^n.""" n = len(sayilar) return [sum(sayilar[i] for i in range(n) if m >> i & 1) for m in range(1 << n)] def uzun_hakem(sayilar, hedef, sertifika): adim = 0 for t in sertifika: adim += 1 if t == hedef: return True, adim return False, adim ORN = ornekler() print("sertifika uzunluk hakem adimi butce 13 butce 100 butce 10000") for ad, uret, hkm in (("indis listesi ", kisa_sertifika, kisa_hakem), ("yalniz 'evet' ", lambda s, h: [], bos_hakem), ("butun toplamlar", uzun_sertifika, uzun_hakem)): uz = ha = 0 b13 = b100 = b1e4 = 0 for o in ORN: sert = uret(o["sayilar"], o["hedef"]) ok, a = hkm(o["sayilar"], o["hedef"], sert) uz += len(sert) ha += a b13 += a <= 13 b100 += a <= 100 b1e4 += a <= 10000 print(f"{ad:15s} {uz:7d} {ha:11d} {b13:8d} {b100:9d} {b1e4:11d}") ``` ``` sertifika uzunluk hakem adimi butce 13 butce 100 butce 10000 indis listesi 81 101 20 20 20 yalniz 'evet' 0 4321 0 7 20 butun toplamlar 81920 4321 0 7 20 ``` Üç satır aynı yanıtı üretiyor ama üç ayrı iş yapıyor. İlk satırda toplam sertifika uzunluğu **81 indis** ve hakem **101 adım** harcıyor. İkinci satırda sertifika boş: hakem hiçbir tanık almadığı için baştan aramak zorunda ve **4321 adım** harcıyor; bu bir hakem değil, çözücüdür. Üçüncü satır daha sinsidir. Sertifika var, hatta çok var — toplam **81.920 sayı**, yani örnek başına 4096 — ve hakem gerçekten yalnız okuyor, aramıyor. Ama okuduğu şey girdiden üstel olarak uzun olduğu için adım sayısı yine **4321**. Bütçe sütunları farkı kapatıyor: bütçe 13'te yalnız ilk tasarım 20'de 20 veriyor, ötekiler sıfırda. Uzunluk sınırı olmasaydı her problem için "doğrulanabilir" bir tasarım kurulabilirdi ve NP bütün karar problemlerini içerirdi. **Tanımdaki kısalık koşulu, tanımı boş olmaktan kurtaran şeydir.** M01/K07 İleri Algoritmalar kursu bu farkı başka bir problemde çoktan ölçmüştü: Hamilton yolu dersinde bir aday yolu doğrulamak çizge başına 7 adım, yolu bulmak ortalama 61 adım tutuyordu ve on iki düğümde doğrulama 11 adımken yol olmadığını göstermek ortalama 11.601 adıma çıkıyordu. O ders farkı ölçüp adlandırmayı buraya bırakmıştı; adı **doğrulanabilirlik**, sınıfı **NP**'dir. ## Uçurum Girdi Boyuyla Ne Yapıyor Yirmi örnekteki 42,8 oranı tek bir girdi büyüklüğünde alınmış bir sayıdır. İkinci süpürme girdi boyunu değiştirir ve iki tarafın **en kötü durumdaki** adımını yan yana koyar. Bu tablo hiçbir örnek koşturmaz; iki sayıyı doğrudan hesaplar, çünkü ikisi de girdiye bakmadan yazılabilir. ```python print(" n cozme (en kotu) dogrulama (en kotu) oran") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {1 << n:15d} {n + 1:19d} {(1 << n) // (n + 1):9d}") ``` ``` n cozme (en kotu) dogrulama (en kotu) oran 8 256 9 28 12 4096 13 315 16 65536 17 3855 20 1048576 21 49932 24 16777216 25 671088 ``` Sol sütun her satırda ikiye katlanarak ilerliyor: 256, 4096, 65.536, 1.048.576, 16.777.216. Orta sütun birer birer artıyor: 9, 13, 17, 21, 25. Oran 28'den **671.088**'e çıkıyor. Girdi boyu üç katına çıkarken açıklık yirmi dört bin katına çıkıyor. Tablodaki sol sütun bir uyarı taşır. **16.777.216 sayısı, bu problemin bedeli değildir; buradaki çözücünün bedelidir.** Aynı problem için daha az adım harcayan bir yordam olup olmadığı burada ölçülmedi. Ölçülen tek şey, tam taramanın 24 sayıda kaç alt küme göreceğidir. Sağ sütun ise problemin kendisine daha yakındır: sertifika verildiğinde n+1 adım yeter, ve bu sınır yordam seçiminden bağımsızdır. ## Doğrulanabilirlik Neyi Vaat Etmez Bir problemin NP sınıfında olması, o problemin ucuz olduğunu **söylemez**. NP, yalnız şunu söyler: doğru yanıt "evet" ise, bunu size gösterecek kısa bir tanık **vardır**. Tanığın nasıl bulunacağı hakkında hiçbir şey söylemez, ve bu ders o bulmanın 4321 adım sürdüğünü ölçtü. Ayrım mühendislikte doğrudan karşılık bulur. Bir sistemde bir yerleşim planının, bir çizelgenin ya da bir yapılandırmanın **geçerli** olduğunu sınamak çoğu zaman ucuzdur ve ölçülebilir. Aynı planı **üretmek** bambaşka bir iştir. Bir raporda "doğrulama 13 adım" ile "üretim 4096 adım" sayıları yan yana yazılmadıkça, "sistem planı doğruluyor" cümlesi hangi işin yapıldığını söylemez. Sınıfın adı da bir uyarı taşır. NP, "belirlenimci olmayan polinom zaman" ifadesinin kısaltmasıdır ve buradaki belirlenimsizlik bir makine tasarımına değil, **tanığın verilmiş sayılmasına** karşılık gelir. Sınıfın adını "polinom değil" diye okumak yaygın bir yanlıştır ve bu dersin ölçtüğü her sayıyı ters çevirir: P sınıfındaki eşik problemi de NP sınıfındadır, çünkü hakem sertifikaya hiç bakmadan 13 adımda yanıtı kurar. Son bir sınır: bu derste ölçülen hiçbir sayı, alt küme toplamı probleminin NP sınıfında olduğunu **kanıtlamaz**. Kanıtlayan şey, hakemin yapısıdır — sertifika en çok n indis taşır ve hakem en çok n+1 adım harcar, her girdide. Ölçüm bu yapıyı sınadı ve 20 örnekte tutarlı buldu; bu bir sınamadır, kanıtın yerine geçmez. ## Özet - Sertifika, bir "evet" yanıtını arama yapmadan sınanabilir kılan tanıktır; hakem sertifikayı okur, aramaz. - Aynı 20 örnekte çözme 4321, doğrulama 101 adım harcıyor ve oran 42,8; en uzun sertifika 5 indis, girdi ise 12 sayı. - Adım bütçesi 13'te sertifikayla 20 örneğin 20'si karara bağlanıyor, çözerek hiçbiri; bütçeyi 10.000'e çıkarmak sertifika sütununda hiçbir şeyi değiştirmiyor. - Bir indisi düşürülmüş sertifika 20 örneğin 20'sinde reddediliyor; hakem kabul ettiği kadar reddetmekle de sınanır. - Girdi boyu 8'den 24'e çıkarken çözmenin en kötüsü 256'dan 16.777.216'ya, doğrulama 9'dan 25'e gidiyor ve oran 671.088'e çıkıyor. - NP sınıfında olmak ucuzluk vaat etmez; yalnız "evet" yanıtının kısa bir tanığı olduğunu söyler ve tanığın nasıl bulunacağı hakkında hiçbir şey söylemez. ## Sonraki Adım Bu derste tek bir problem ölçüldü. Ama zorluk hakkında söylenen çoğu cümle tek bir problem hakkında değildir: "şu problem en az şu kadar zor" biçiminde, iki problemi karşılaştıran bir cümledir. Sonraki ders bu karşılaştırmanın nasıl kurulduğunu sayar: bir problemi bir başkasına çeviren dönüşümün kaç adım tuttuğunu, dönüşümün yanıtı koruyup korumadığını, ve çevirinin neden zorluğu **taşıdığını** ama **azaltmadığını**.