NP Sınıfı

Ö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.

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.

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.

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ı.