co-NP ve Sınıflar Arası İlişkiler

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.

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.

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.

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.