--- title: 'co-NP ve Sınıflar Arası İlişkiler' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/co-np-ve-siniflar-arasi-iliskiler' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:29+00:00' license: 'CC BY-SA 4.0' --- # co-NP ve Sınıflar Arası İlişkiler Tümleyen problemlerin durumu ve evet ile hayır yanıtları arasındaki ölçülmüş asimetri: 20 örnekte evet sertifikası 101 adımda kapanırken hayır yanıtı tam tarama ile 81.920 adım istiyor. Yapılı hayır örneklerinde 260 adımlık kısa bir kanıt 20/20 çalışıyor, yapısız örneklerde aynı kanıt 20/20 hiçbir şey söyleyemiyor. Girdi boyu 24'te evet sertifikası 25, hayır kanıtı 16.777.216 adım. Eşik problemi iki yönde de 260 adımda kapanıyor. Buraya kadar ölçülen her şey **evet** yönündeydi: sertifika bir "evet"i doğruluyordu, indirgeme bir "evet"i taşıyordu. Bir yanıt "hayır" olduğunda ne gösterilebilir. Bu ders eksik yönü ölçer ve iki yönün simetrik olmadığını sayar. Sorunun kaynağı NP tanımının kendisindedir. Tanım yalnız "evet" yanıtı için bir tanık ister; "hayır" yanıtı için hiçbir şey vaat etmez. M01/K07 İleri Algoritmalar kursu bu asimetriyi Hamilton yolu dersinde çoktan gözlemişti: yol bulunmayan çizgelerin **hepsinde** karar yordamı sayma yordamının gezdiği ağacın tamamını gezmişti. O gözlem burada bir sınıf ayrımına dönüşür. - **KS29.** Bir karar probleminin **tümleyeni**, aynı girdide yanıtı ters çevrilmiş problemdir: "hedefe toplanan bir alt küme var mı" sorusunun tümleyeni "hiçbir alt küme hedefe toplanmıyor mu" sorusudur. - **KS30.** **co-NP**, tümleyeni NP sınıfında olan karar problemlerinin sınıfıdır. Eşdeğer okunuşu şudur: **"hayır" yanıtının kısa ve hızlı sınanabilir bir tanığı olan** problemler. - **KS31.** Üç örnek kümesi kurulur. **Evet kümesi:** ortak tanımın 20 örneği. **Yapılı hayır kümesi:** bütün sayılar ikiye katlanır, hedef tek yapılır. **Yapısız hayır kümesi:** aynı sayılar, hedef olarak erişilemeyen bir değer seçilir. - **KS32.** Yapısız kümenin hedefi seçilirken erişilen toplamlar tam olarak çıkarılır. Bu bir **kurulum adımıdır**, hakem değildir, ve adımı ölçüme katılmaz. - **KS33.** **Kısa hayır kanıtı** yalnız bir gerek koşulu sınar: bütün sayılar çiftse toplamları da çifttir, dolayısıyla tek bir hedefe ulaşılamaz. Bu kanıt "hayır" diyebilir, "evet" diyemez; diyemediğinde **bilinmiyor** döner. - **KS34.** Bir adım, kısa kanıt için **bir sayı okumasıdır**; tam tarama için **bir alt kümedir**. - **KS35.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. - **KS36.** Örnekler ortak tanımın üretecinden, tohum **20260218**. İkinci tohum yoktur. - **KS37.** NP ile co-NP'nin eşit olup olmadığı **açık bir sorudur** ve bu derste yanıtlanmaz. Ölçüm yalnız belirli kanıtların belirli örneklerde çalışıp çalışmadığını sayar. ## Tümleyen Neden Ayrı Bir Soru Bir karar problemini çözen yordam, tümleyenini de çözer: yanıtı ters çevirmek bir adım bile tutmaz. Bu yüzden **çözülebilirlik** açısından bir problem ile tümleyeni arasında fark yoktur, ve P sınıfı tümleyen almaya kapalıdır — P'deki bir problemin tümleyeni de P'dedir. Doğrulanabilirlik açısından durum başkadır. "Şu alt küme hedefe toplanıyor" tanığı, "hiçbir alt küme toplanmıyor" iddiasını desteklemez; tersine, o iddiayı çürütür. "Hiçbiri" demek için gösterilecek şeyin ne olduğu ayrı bir tasarım sorusudur ve her problem için bir yanıtı olduğu **bilinmez**. Bu yüzden NP ile co-NP ayrı adlar taşır. Alt küme toplamının NP sınıfında olduğu `02`'de gösterildi; co-NP sınıfında olup olmadığı gösterilmedi ve bu ders de göstermez. ## İki Yönün Ölçülmesi Aşağıdaki blok üç örnek kümesini aynı hakemle koşturur, sonra her kümede iki ayrı kısa kanıt dener: "evet" için sertifika, "hayır" için çift-tek gerek koşulu. ```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 hakem(sayilar, hedef): """Tam tarama. 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 evet_dogrula(sayilar, hedef, sertifika): """Bir adim = bir indis okumasi.""" adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 def hayir_dogrula(sayilar, hedef): """Tek yone calisan kisa kanit: butun sayilar cift ise toplamlari da cifttir , dolayisiyla tek bir hedefe ulasilamaz.""" adim = 0 for s in sayilar: adim += 1 if s % 2: return "bilinmiyor", adim adim += 1 return ("hayir", adim) if hedef % 2 else ("bilinmiyor", adim) def ulasilmayan(sayilar): """Kurulum adimi (hakem degil): erisilen toplamlar cikarilir ve ucte bire en yakin erisilmeyen deger secilir.""" 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)) ORN = ornekler() EVET = [(o["sayilar"], o["hedef"]) for o in ORN] YAPILI = [([2 * x for x in o["sayilar"]], 2 * o["hedef"] + 1) for o in ORN] YAPISIZ = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ORN] print("kume hakem yaniti tam tarama adimi") for ad, kume, bekle in (("evet ", EVET, True), ("yapili ", YAPILI, False), ("yapisiz", YAPISIZ, False)): top = sum(hakem(s, h)[1] for s, h in kume) uyan = sum(1 for s, h in kume if hakem(s, h)[0] == bekle) print(f"{ad} {uyan:2d}/20 beklenen {top:16d}") print() es = sum(evet_dogrula(s, h, hakem(s, h)[2])[1] for s, h in EVET) print("evet sertifikasi (20 ornek) dogrulama adimi:", es) for ad, kume in (("yapili ", YAPILI), ("yapisiz", YAPISIZ)): hy = sum(1 for s, h in kume if hayir_dogrula(s, h)[0] == "hayir") ha = sum(hayir_dogrula(s, h)[1] for s, h in kume) print(f"kisa hayir kaniti {ad} | 'hayir' diyebildigi: {hy:2d}/20 | adim: {ha}") print() print("butce evet sertifikasi yapili hayir kaniti yapisiz tam tarama") for b in (13, 100, 1000, 10000): a1 = sum(1 for s, h in EVET if evet_dogrula(s, h, hakem(s, h)[2])[1] <= b) a2 = sum(1 for s, h in YAPILI if hayir_dogrula(s, h)[0] == "hayir" and hayir_dogrula(s, h)[1] <= b) a3 = sum(1 for s, h in YAPISIZ if hakem(s, h)[1] <= b) print(f"{b:5d} {a1:16d} {a2:19d} {a3:19d}") ``` ``` kume hakem yaniti tam tarama adimi evet 20/20 beklenen 4321 yapili 20/20 beklenen 81920 yapisiz 20/20 beklenen 81920 evet sertifikasi (20 ornek) dogrulama adimi: 101 kisa hayir kaniti yapili | 'hayir' diyebildigi: 20/20 | adim: 260 kisa hayir kaniti yapisiz | 'hayir' diyebildigi: 0/20 | adim: 39 butce evet sertifikasi yapili hayir kaniti yapisiz tam tarama 13 20 20 0 100 20 20 0 1000 20 20 0 10000 20 20 20 ``` ## Asimetrinin Okunması İlk tablo tek başına asimetriyi kuruyor. Evet kümesinde tam tarama **4321 adım** harcıyor, çünkü uyan bir alt küme bulununca duruyor. İki hayır kümesinde ise **81.920 adım** — yani örnek başına tam **4096**, hiçbir indirim yok. Sayı iki kümede birebir aynı çünkü nedeni yordamsal değil mantıksaldır: "hiçbiri" demek için görülmemiş tek bir alt küme kalmamalıdır. İkinci blok üç sayıyı yan yana getiriyor. **Evet sertifikası 101 adım.** **Yapılı hayır kanıtı 260 adım** ve 20 örneğin 20'sinde "hayır" diyebiliyor. **Yapısız hayır kanıtı 39 adım** harcıyor ve 20 örneğin **hiçbirinde** bir şey söyleyemiyor — ilk tek sayıyı görünce çekiliyor. Bu üçlü, co-NP tanımının neden bir varlık iddiası olduğunu gösteriyor. Kısa bir "hayır" tanığı **bazı örnekler için vardır** ve ölçüldü: 4096 adım yerine 13. Ama tanığın **her** örnek için var olması ayrı bir iddiadır ve yapısız küme bu iddianın kendiliğinden sağlanmadığını gösteriyor. Ölçümün söylediği şey şudur: **bu kanıt bu örneklerde çalışmadı.** Söylemediği şey ise, başka bir kısa kanıtın var olmadığıdır; öyle bir kanıt aranmadı, yalnız bu bir tane denendi. Bütçe süpürmesi aynı ayrımı bir kez daha veriyor. Evet sertifikası ve yapılı hayır kanıtı bütçe 13'te doluyor; bütçeyi bin katına çıkarmak ikisinde de hiçbir şey değiştirmiyor. Yapısız küme ise 1000'de hâlâ sıfırda ve ancak 10.000'de 20'ye çıkıyor. ## İki Yönü de Ucuz Olan Problem Her problemde bu asimetri yoktur. Eşik problemi — sayıların toplamı hedefi aşıyor mu — iki yönde de aynı yordamla kapanır: toplam bir kez hesaplanır ve 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 esik(sayilar, hedef): """Toplam hedefi asiyor mu. Iki yon de ayni yordamla kapanir.""" toplam, adim = 0, 0 for s in sayilar: toplam += s adim += 1 return toplam > hedef, adim + 1 ev = hy = ea = ha = 0 for o in ornekler(): y1, a1 = esik(o["sayilar"], o["hedef"]) y2, a2 = esik(o["sayilar"], sum(o["sayilar"]) + 1) ev, hy = ev + y1, hy + (not y2) ea, ha = ea + a1, ha + a2 print("esik problemi | evet:", ev, "/20 ,", ea, "adim | hayir:", hy, "/20 ,", ha, "adim") print() print(" n evet sertifikasi hayir kaniti (tam tarama)") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 1:16d} {1 << n:25d}") ``` ``` esik problemi | evet: 20 /20 , 260 adim | hayir: 20 /20 , 260 adim n evet sertifikasi hayir kaniti (tam tarama) 8 9 256 12 13 4096 16 17 65536 20 21 1048576 24 25 16777216 ``` Eşik probleminde iki yön de **260 adım**: birebir eşit, ve eşitlik bir rastlantı değil yordamın yapısından geliyor. Bu problem hem NP hem co-NP sınıfındadır, çünkü P sınıfındadır ve P her iki sınıfın da içindedir. Yanıtın yönü maliyeti değiştirmiyor. Alt satırdaki tablo karşıt uçtur. Girdi boyu 8'den 24'e çıkarken evet sertifikası 9'dan **25** adıma, hayır kanıtı 256'dan **16.777.216** adıma gidiyor. İki sütun aynı problemin iki yüzüdür ve aynı hızda büyümüyorlar. ## Aynı Hayır, Daha Az Adım Yapısız kümede tam taramanın 81.920 adım harcaması, o örnekler için "hayır" demenin bedeli **değildir**; yalnız tam taramanın bedelidir. Bunu göstermenin yolu, aynı yanıtı daha az adımda kuran başka bir yordam denemektir. Aşağıdaki blok iki tane dener: kısmi toplam hedefi aştığında dalı kesen budamalı bir tarama, ve `01`'de tanıtılan erişilen toplamlar tablosu. ```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): 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 budamali(sayilar, hedef): """Kismi toplam hedefi asinca dal kesilir. Bir adim = bir dugum.""" s = sorted(sayilar) n, adim = len(s), 0 def gez(i, toplam): nonlocal adim adim += 1 if toplam == hedef: return True if toplam > hedef or i == n: return False return gez(i + 1, toplam + s[i]) or gez(i + 1, toplam) return gez(0, 0), adim def dinamik(sayilar, hedef): """Erisilen toplamlar tablosu. Bir adim = bir tablo hucresi.""" ulasilan = [False] * (hedef + 1) ulasilan[0] = True adim = 0 for x in sayilar: for t in range(hedef, x - 1, -1): adim += 1 if ulasilan[t - x]: ulasilan[t] = True return ulasilan[hedef], adim YAPISIZ = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ornekler()] print("yordam hayir diyen toplam adim butce 1000 butce 10000") for ad, f in (("tam tarama ", tam_tarama), ("budamali tarama", budamali), ("dinamik tablo ", dinamik)): hy = top = b3 = b4 = 0 for s, h in YAPISIZ: y, a = f(s, h) hy += not y top += a b3 += a <= 1000 b4 += a <= 10000 print(f"{ad:15s} {hy:11d} {top:11d} {b3:10d} {b4:11d}") ``` ``` yordam hayir diyen toplam adim butce 1000 butce 10000 tam tarama 20 81920 0 20 budamali tarama 20 21594 12 20 dinamik tablo 20 15736 16 20 ``` Üç yordam da 20 örneğin 20'sinde "hayır" diyor, yani üçü de aynı yanıtı kuruyor. Adım sayıları ise **81.920**, **21.594** ve **15.736**: budamalı tarama tam taramanın dörtte birinden azını, tablo yordamı beşte birinden azını harcıyor. Bütçe 1000'de tam tarama sıfırda kalırken budamalı tarama 12, tablo yordamı 16 örneği karara bağlıyor. Bir bölüm önce "bu kanıt bu örneklerde çalışmadı" denmişti; şimdi aynı örnekler dört beş kat ucuza kapanıyor. Yine de kapanma **n+1 adıma** inmedi ve tablo yordamının ucuzluğu `01`'de görüldüğü gibi hedefin değerine bağlıdır. Sonuç iki cümleye sığar: **ölçülen en iyi sayı, ölçülebilecek en iyi sayı değildir**; ve daha iyi bir sayı bulmak, bir sınır kanıtlamakla aynı şey değildir. ## Bilinen ve Açık Olan Bilinenler kısadır. **P sınıfı hem NP'nin hem co-NP'nin içindedir**, ve tümleyen almaya kapalıdır. **NP-tam bir problemin tümleyeninin NP sınıfında olduğu bilinmiyor.** Bir problem hem NP hem co-NP sınıfındaysa, iki yönde de kısa tanığı var demektir; bu güçlü bir özelliktir ve her problemde bulunmaz. Açık olan da kısadır: **NP ile co-NP'nin eşit olup olmadığı bilinmiyor.** Bu ders o soruyu yanıtlamaz ve yanıtlamaya çalışmaz. Ölçtüğü şey, tek bir kısa kanıtın 20 örnekte çalışıp 20 örnekte çalışmadığıdır. Yapısız kümede kanıtın 0/20 vermesi, o örnekler için kısa bir kanıt **olmadığını göstermez**; yalnız **bu** kanıtın onlara uymadığını gösterir. Bu ayrım kursun aşırı iddia yasağının doğrudan uygulanmasıdır. Mühendislik karşılığı somuttur. Bir doğrulayıcıda "geçerli" yanıtını gerekçelendirmek ile "geçersiz" yanıtını gerekçelendirmek iki ayrı iştir: ilki bir tanık gösterebilir, ikincisi çoğu zaman "her ihtimali gördüm" demek zorundadır. İki yönün adım sayısı ayrı yazılmadıkça doğrulayıcının maliyeti bilinmiş sayılmaz. ## Özet - Bir problemin tümleyeni, çözülebilirlik açısından ondan farksızdır; doğrulanabilirlik açısından ayrı bir sorudur, çünkü sertifika ters çevrilerek kullanılamaz. - Evet kümesinde tam tarama 4321 adım harcıyor, iki hayır kümesinde 81.920 adım — örnek başına 4096, hiçbir indirim yok. - Kısa hayır kanıtı yapılı örneklerin 20'sinde 20'sinde çalışıyor ve 260 adım tutuyor; yapısız örneklerin hiçbirinde bir şey söyleyemiyor ve 39 adımda çekiliyor. - Eşik probleminde iki yön de 260 adımda kapanıyor; bu problem P sınıfında olduğu için hem NP hem co-NP sınıfındadır. - Girdi boyu 8'den 24'e çıkarken evet sertifikası 9'dan 25 adıma, hayır kanıtı 256'dan 16.777.216 adıma gidiyor. - NP ile co-NP'nin eşit olup olmadığı açık bir sorudur; bir kanıtın bu örneklerde çalışmaması, hiçbir kısa kanıtın olmadığını göstermez. ## Sonraki Adım Bu dersle birlikte 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. Sonraki ders bu soruyu ifade eder ve **ölçemeyeceğini ölçmeye çalışmaz.** Ölçebildiği tek şey bilinen en iyi yordam ile bilinen alt sınır arasındaki farktır; o fark daraltılabiliyor mu, daraltılınca kapanıyor mu, ve daralmanın kendisi bir yön göstergesi sayılabilir mi.