--- title: 'NP-Tam ve NP-Zor' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/np-tam-ve-np-zor' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:30+00:00' license: 'CC BY-SA 4.0' --- # NP-Tam ve NP-Zor İndirgeme yoluyla zorluk aktarımının adım sayısıyla ölçülmesi: alt küme toplamı örneğini bölüştürme örneğine çeviren dönüşüm 15 adım tutuyor, kaynağı çözmenin 0,2632'si. Yirmi örnekte indirgeme 300, kaynağı çözme 4321, hedefi çözme 19.847 adım ve 20 örneğin 20'sinde iki yanıt uyuşuyor. Girdi boyu 24'te indirgeme 27 adımda kalırken çözme 16.777.216 adıma çıkıyor. Çevirinin yönünün neyi kanıtlayıp neyi kanıtlamadığı ayrıca yazılıyor. Önceki ders tek bir problem ölçtü. Ama zorluk hakkında söylenen cümlelerin çoğu 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. Böyle bir cümle nasıl kurulur ve bedeli nedir. Araç, M01/K07 İleri Algoritmalar kursunda tanıtılan **indirgemedir**: bir problemin örneğini, başka bir problemin örneğine çeviren dönüşüm. O kursta indirgeme bir çözüm tekniğiydi — tanıdık bir kalıba çevirip kalıbın yordamını kullanmak. Burada aynı dönüşüm başka bir iş için kullanılır: **bir problemin zorluğunu bir başkasına aktarmak.** Yordam tekrarlanmaz; sayıya çevrilir. - **KS20.** **Kaynak problem** alt küme toplamıdır: bir alt kümenin toplamı hedefe eşit mi. **Hedef problem** bölüştürmedir: sayılar, toplamları eşit iki paya ayrılabilir mi. - **KS21.** **İndirgeme**, kaynağın bir örneğini hedefin bir örneğine çeviren yordamdır ve yanıtı **korumak zorundadır**: kaynak "evet" ise hedef de "evet", kaynak "hayır" ise hedef de "hayır" vermelidir. - **KS22.** İndirgemede bir adım, **bir eleman kopyalamasıdır**; toplam alma ve eklenen elemanın hesabı için üç adım daha sayılır. - **KS23.** İndirgemenin doğruluğu **varsayılmaz, sınanır**: 20 örneğin her birinde iki yanıt karşılaştırılır ve uyuşan örnek sayısı yazılır. - **KS24.** Üç adım sayısı ayrı tutulur: **indirgeme**, **kaynağı çözme**, **hedefi çözme**. İkincisi ile üçüncüsü karıştırılırsa indirgemenin ne yaptığı görünmez olur. - **KS25.** İndirgemenin **yönü** yazılır. Kaynaktan hedefe indirgeme, **hedef en az kaynak kadar zordur** der; ters yönü söylemez. - **KS26.** Bütçe süpürmesi dört değerde yapılır: 15, 100, 1000, 10.000 adım. - **KS27.** Örnekler ortak tanımın üretecinden, tohum **20260218**, 20 örnek, örnek başına 12 sayı. İkinci tohum yoktur. - **KS28.** Hiçbir problemin NP-tam olduğu **koşumla gösterilmez**. Koşum yalnız tek bir indirgemenin adımını ve doğruluğunu ölçer. ## Zorluğu Aktarmak Ne Demek İndirgemenin okunma biçimi ters sezgiseldir ve yanlış okunması yaygındır. Kaynak problemin bir örneği hedef problemin bir örneğine çevriliyorsa, **hedefi çözebilen her yordam kaynağı da çözebilir**: önce çevir, sonra hedefi çöz, yanıtı olduğu gibi al. Bunun sonucu şudur — hedef problem için ucuz bir yordam bulunursa, kaynak problem için de ucuz bir yordam olurdu. Buradan çıkan cümle **hedef hakkındadır**: hedef, kaynaktan **daha kolay olamaz**. Çeviri kaynağı ucuzlatmaz; hedefin ucuzlama ihtimalini kaynağa bağlar. Yön karıştırılırsa cümle tersine döner ve hiçbir şey söylemez hale gelir. İki sınıf adı bu okumanın üzerine kurulur. Bir problem, **NP sınıfındaki her problem ona indirgenebiliyorsa** NP-zordur. Bir problem hem **NP-zor** hem de **NP sınıfındaysa**, yani kendi "evet" yanıtının kısa bir sertifikası varsa, **NP-tamdır**. Fark tek bir koşuldadır: NP-zor bir problem NP sınıfında olmak zorunda değildir, hatta bir karar problemi olmak zorunda bile değildir. ## Bir İndirgemenin Ölçülmesi Aşağıdaki dönüşüm şunu yapar: sayıların toplamı $T$, hedef $h$ olsun; listeye tek bir yeni eleman eklenir. Bu eleman, toplamın iki eşit paya bölünebilmesini ancak kaynakta $h$'ye toplanan bir alt küme varsa mümkün kılacak biçimde seçilir. Dönüşümün yanıtı koruyup korumadığı varsayılmaz; her örnekte sınanı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 alt_kume_hakem(sayilar, hedef): """Kaynak problem: bir alt kumenin toplami hedefe esit mi.""" 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 indirge(sayilar, hedef): """Alt kume toplami ornegini iki esit paya bolusturme ornegine cevirir. Bir adim = bir eleman kopyalamasi; uc adim da toplam ve ek eleman icin.""" toplam = sum(sayilar) yeni = list(sayilar) + [2 * hedef - toplam] if 2 * hedef >= toplam else \ list(sayilar) + [toplam - 2 * hedef] return yeni, len(sayilar) + 3 def bolusturme_hakem(sayilar): """Hedef problem: sayilar iki esit toplamli paya bolunebilir mi.""" toplam = sum(sayilar) if toplam % 2: return False, 1 var, adim = alt_kume_hakem(sayilar, toplam // 2) return var, adim + 1 ORN = ornekler() uyusan, ia, ka, ha = 0, 0, 0, 0 for o in ORN: var1, a1 = alt_kume_hakem(o["sayilar"], o["hedef"]) yeni, ad = indirge(o["sayilar"], o["hedef"]) var2, a2 = bolusturme_hakem(yeni) uyusan += var1 == var2 ia, ka, ha = ia + ad, ka + a1, ha + a2 print("20 ornek , n=12 | yaniti uyusan:", uyusan, "/ 20") print(" indirgeme:", ia, "adim | kaynagi cozme:", ka, "adim | hedefi cozme:", ha, "adim") print(" indirgemenin kaynagi cozmeye orani:", round(ia / ka, 4)) print() o = ORN[0] yeni, ad = indirge(o["sayilar"], o["hedef"]) var1, a1 = alt_kume_hakem(o["sayilar"], o["hedef"]) var2, a2 = bolusturme_hakem(yeni) print("ilk ornek | indirgeme", ad, "adim | kaynak yanit", var1, f"({a1} adim)", "| hedef yanit", var2, f"({a2} adim)") print(" oran:", round(ad / a1, 4)) print() print("butce indirgenen kaynagi cozulen hedefi cozulen") for b in (15, 100, 1000, 10000): i1 = sum(1 for x in ORN if indirge(x["sayilar"], x["hedef"])[1] <= b) k1 = sum(1 for x in ORN if alt_kume_hakem(x["sayilar"], x["hedef"])[1] <= b) h1 = sum(1 for x in ORN if bolusturme_hakem(indirge(x["sayilar"], x["hedef"])[0])[1] <= b) print(f"{b:5d} {i1:10d} {k1:15d} {h1:14d}") ``` ``` 20 ornek , n=12 | yaniti uyusan: 20 / 20 indirgeme: 300 adim | kaynagi cozme: 4321 adim | hedefi cozme: 19847 adim indirgemenin kaynagi cozmeye orani: 0.0694 ilk ornek | indirgeme 15 adim | kaynak yanit True (57 adim) | hedef yanit True (288 adim) oran: 0.2632 butce indirgenen kaynagi cozulen hedefi cozulen 15 20 0 0 100 20 7 0 1000 20 19 12 10000 20 20 20 ``` ## İndirgeme Ucuz, Çözme Değil İlk örnek üç sayıyı yan yana koyuyor: **indirgeme 15 adım**, **kaynağı çözme 57 adım**, **hedefi çözme 288 adım**. İndirgeme, kaynağı çözmenin **0,2632**'si kadar. Yirmi örneğin toplamında oran daha da düşüyor: 300'e karşı 4321, yani **0,0694**. İkinci sayı çifti daha öğreticidir. Hedefi çözmek **19.847 adım** tutuyor, kaynağı çözmenin neredeyse beş katı. Çeviri hiçbir şeyi ucuzlatmadı; tersine, listeye bir eleman eklediği için hedef örnek kaynaktan **daha pahalı** hale geldi. İndirgemenin işi ucuzlatmak değildir. İşi, iki problemin zorluğu arasında bir **bağ** kurmaktır, ve bu bağ kurulurken hesap ucuza gelir. Doğruluk sütunu bu bağın ön koşuludur: 20 örneğin **20'sinde** iki yanıt uyuşuyor. Uyuşmasaydı indirgeme geçersiz olurdu ve adım sayısının hiçbir anlamı kalmazdı. Yirmi örnekte uyuşması ise dönüşümün her girdide doğru olduğunu **kanıtlamaz**; dönüşümün doğruluğu, eklenen elemanın seçiminden gelen bir gerekçedir ve ölçüm o gerekçeyi yalnız sınar. Bütçe süpürmesi üç sütunda üç ayrı davranış gösteriyor. **İndirgeme sütunu bütçe 15'te dolu** ve 10.000'de hâlâ 20; bütçeyi büyütmek hiçbir şey eklemiyor. Kaynağı çözme 0'dan 7'ye, 19'a, 20'ye çıkıyor. Hedefi çözme daha geç açılıyor: 1000'de yalnız 12, 10.000'de 20. Aynı bütçe, çevrilmiş örnek için daha az yetiyor. ## Girdi Boyu Büyüdüğünde Ne Kalıyor Tek bir girdi büyüklüğünde alınan 0,2632 oranı, indirgemenin ucuzluğunu tam olarak anlatmaz. Asıl soru, girdi büyüklüğü büyüdüğünde iki tarafın **birbirine göre** ne yaptığıdır. ```python print(" n indirgeme kaynagi cozme hedefi cozme indirgeme/cozme") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 3:9d} {1 << n:13d} {1 << (n + 1):12d}" f" {(n + 3) / (1 << n):15.6f}") ``` ``` n indirgeme kaynagi cozme hedefi cozme indirgeme/cozme 8 11 256 512 0.042969 12 15 4096 8192 0.003662 16 19 65536 131072 0.000290 20 23 1048576 2097152 0.000022 24 27 16777216 33554432 0.000002 ``` İndirgeme sütunu 11, 15, 19, 23, 27: girdi büyüklüğüyle birer birer, düz. Çözme sütunları her satırda ikiye katlanıyor. Oran 0,042969'dan **0,000002**'ye iniyor. Girdi boyu üç katına çıkarken indirgemenin payı yirmi bin kat küçülüyor. Bu tablonun taşıdığı sonuç şudur: **indirgemenin bedeli, aktardığı zorluğun yanında yok sayılabilir hale geliyor.** Bir problemin zor olduğu biliniyorsa ve o problem ucuz bir dönüşümle başka bir probleme çevrilebiliyorsa, ikinci problem hakkında söylenecek söz birinciden gelir. Zorluk taşınabilir bir şeydir ve taşıma masrafı düşüktür. ## Yanlış Bir Çevirim Nasıl Görünür İndirgemenin ucuzluğu tek başına bir erdem değildir. Daha ucuz ama **yanıtı korumayan** bir çevirim her zaman kurulabilir, ve ucuzluğuna bakarak ayırt edilemez. Aşağıdaki blok doğru çevirimin yanına, hedefi düpedüz atan bir çevirimi koyar. Üçüncü ölçüm ters yöndedir: bölüştürme örneği alt küme toplamı örneğine çevrilir. ```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 alt_kume_hakem(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 bolusturme_hakem(sayilar): toplam = sum(sayilar) if toplam % 2: return False, 1 var, adim = alt_kume_hakem(sayilar, toplam // 2) return var, adim + 1 def dogru_indirge(sayilar, hedef): """Yaniti koruyan cevirim: tek bir denklestirici eleman eklenir.""" toplam = sum(sayilar) ek = 2 * hedef - toplam if 2 * hedef >= toplam else toplam - 2 * hedef return list(sayilar) + [ek], len(sayilar) + 3 def naif_indirge(sayilar, hedef): """Hedefi atan cevirim: liste oldugu gibi bolusturmeye verilir.""" return list(sayilar), len(sayilar) def ters_indirge(sayilar): """Bolusturme ornegini alt kume toplami ornegine cevirir.""" toplam = sum(sayilar) return list(sayilar), toplam // 2, len(sayilar) + 1 print("cevirim uyusan ayrilan cevirim adimi") for ad, f in (("dogru", dogru_indirge), ("naif ", naif_indirge)): uyusan = ayrilan = ca = 0 for o in ornekler(): k, _ = alt_kume_hakem(o["sayilar"], o["hedef"]) yeni, adim = f(o["sayilar"], o["hedef"]) h, _ = bolusturme_hakem(yeni) ca += adim if k == h: uyusan += 1 else: ayrilan += 1 print(f"{ad:13s} {uyusan:6d} {ayrilan:7d} {ca:13d}") print() uyusan, ta, ha = 0, 0, 0 for o in ornekler(): yeni, _ = dogru_indirge(o["sayilar"], o["hedef"]) h, a1 = bolusturme_hakem(yeni) s, hedef2, adim = ters_indirge(yeni) k, a2 = alt_kume_hakem(s, hedef2) uyusan += h == k ta, ha = ta + adim, ha + a2 print("ters yon (bolusturme -> alt kume toplami)") print(" uyusan:", uyusan, "/ 20 | cevirim adimi:", ta, "| hedefi cozme adimi:", ha) ``` ``` cevirim uyusan ayrilan cevirim adimi dogru 20 0 300 naif 8 12 240 ters yon (bolusturme -> alt kume toplami) uyusan: 20 / 20 | cevirim adimi: 280 | hedefi cozme adimi: 19827 ``` Naif çevirim **240 adım** harcıyor, doğrusundan **60 adım ucuz**. Ama 20 örneğin **12'sinde** yanlış yanıt veriyor. Yanıtı korumadığı için indirgeme değildir, ve hiçbir zorluk aktarmaz. Sekiz örnekte doğru yanıt vermesi de bir savunma sayılmaz: bir dönüşüm ya her örnekte yanıtı korur ya da geçersizdir. **İndirgemede iş, adım sayısında değil, doğruluk gerekçesindedir.** Naif çevirimin nerede kırıldığı da okunabilir. Bölüştürme sorusu her zaman **toplamın yarısını** sorar; bu örneklerdeki hedef ise toplamın yaklaşık **üçte biridir**. Hedefi atmak, soruyu değiştirmek demektir, ve değişen soru başka bir yanıt verir. Doğru çevirimin eklediği tek eleman tam olarak bu farkı kapatmak içindir: eklenen değer, yarıyı hedefin bulunduğu yere taşır. Ters yön daha kısa: bölüştürme örneği, hedefi toplamın yarısı olan bir alt küme toplamı örneğine **280 adımda** çevriliyor ve 20 örneğin 20'sinde yanıt korunuyor. İki yön birlikte okunduğunda ortaya çıkan sonuç şudur: bu iki problem birbirine **karşılıklı** olarak indirgeniyor, yani birinin ucuz bir yordamı ötekini de ucuzlatır. Zorluk açısından bu iki problem ayrılamaz. ## Koşumun Söylemediği Bu derste ölçülen hiçbir sayı, bölüştürme probleminin NP-tam olduğunu **göstermez**. Gösterilen tek şey, **bir** problemin ona indirgendiğidir. NP-zorluk tanımı, NP sınıfındaki **bütün** problemlerin indirgenebilmesini ister; bu, sonlu bir koşumun kapsayamayacağı bir niceleyicidir. Bu iki problemin NP-tam olduğu kuramın sonucudur ve buraya **kuramın sonucu olarak** girer; yukarıdaki tabloların hiçbiri onu kanıtlamaz. Ölçümün gerçekten kanıtladığı şey daha küçük ve daha somuttur: bu dönüşüm 20 örneğin 20'sinde yanıtı korudu, 15 adım tuttu, ve girdi büyüklüğü büyüdükçe payı düştü. Bir raporda yazılabilecek cümle budur. "Bölüştürme NP-tamdır" cümlesi ise ölçüme değil, kaynağa dayanır ve kaynağı belirtilmeden yazılmaz. Ters yön de açıkça söylenmeli. Kaynaktan hedefe kurulan bir indirgeme, hedefin **en az** kaynak kadar zor olduğunu destekler. Hedefin **en fazla** ne kadar zor olduğu hakkında hiçbir şey söylemez, ve kaynağın kolay olduğunu hiç söylemez. Bir yönde kurulmuş bir bağı iki yönde okumak, bu konudaki en sık hatadır. ## Özet - İndirgeme, bir problemin örneğini başka bir problemin örneğine çeviren ve **yanıtı koruyan** dönüşümdür; yön, hedefin kaynaktan daha kolay olamayacağını söyler. - İlk örnekte indirgeme 15, kaynağı çözme 57, hedefi çözme 288 adım; oran 0,2632. Yirmi örnekte 300'e karşı 4321 ve 19.847. - Çeviri hiçbir şeyi ucuzlatmıyor: hedef örnek bir eleman daha taşıdığı için kaynaktan beş kat pahalıya çözülüyor. - Yirmi örneğin 20'sinde iki yanıt uyuşuyor; bu bir sınamadır, dönüşümün her girdide doğru olduğunun kanıtı değildir. - Girdi boyu 8'den 24'e çıkarken indirgeme 11'den 27 adıma, çözme 256'dan 16.777.216 adıma gidiyor ve oran 0,000002'ye iniyor. - NP-zor, NP sınıfındaki her problemin indirgenebildiği problemdir; NP-tam ise buna ek olarak NP sınıfında olandır. Hiçbiri sonlu bir koşumla gösterilemez. ## Sonraki Adım Buraya kadar ölçülen her şey **evet** yönündeydi: sertifika bir "evet"i doğruluyordu, indirgeme bir "evet"i taşıyordu. Sonraki ders eksik yönü ölçer. Bir yanıt "hayır" olduğunda ne gösterilebilir, ve gösterilecek şey aynı uzunlukta mı. Yirmi örnekte "evet" sertifikası 13 adımda kapanırken "hayır" kanıtının kaç adım istediği, ve bazı "hayır" yanıtlarının neden ucuza kapandığı sayılacak.