NP-Tam ve NP-Zor

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

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.

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.

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.