P–NP Sorusu

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. Bu ders o soruyu ifade eder ve ölçemeyeceğini ölçmeye çalışmaz.

Sorunun neden ölçülemediği ders boyunca sürekli görünür olacak. Ölçüm sonlu bir koşumdur ve sonlu bir koşum ancak “şu yordam şu kadar adım harcadı” der. Soru ise bütün yordamlar üzerine bir niceleyici taşır: “hiçbir yordam yok mu.” Bu iki cümle arasındaki mesafe, bu dersin konusudur. Ölçülebilen tek şey bilinen en iyi yordam ile bilinen alt sınır arasındaki farktır.

• KS38. Soru şu kapsama ilişkisidir: P sınıfı NP sınıfının tamamına eşit midir. P’nin NP’nin içinde olduğu 02’de kuruldu; sorulan şey ters yöndür.
• KS39. Soru açıktır. Bu derste hiçbir yön iddia edilmez, olası sayılmaz, “beklenir” denmez.
• KS40. Bilinen alt sınır, hiçbir yordamın altına inemeyeceği gösterilmiş adım sayısıdır. Burada kullanılan alt sınır en zayıf olanıdır: girdiyi okumadan karar verilemeyeceği için en az n adım.
• KS41. Bilinen en iyi yordam, bu derste kurulan yordamların en azını harcayanıdır. “Bilinen” sözcüğü bu kursun kapsamına göre okunur; kursun dışında daha iyisinin bulunup bulunmadığı burada ölçülmez.
• KS42. İkinci yordam buluşma yordamıdır: girdi ikiye bölünür, ilk yarının bütün alt küme toplamları bir tabloya yazılır, ikinci yarı bu tabloya sorulur.
• KS43. Buluşma yordamının doğruluğu varsayılmaz; her örnekte tam taramanın yanıtıyla karşılaştırılır.
• KS44. Bir adım, tam tarama için bir alt küme, buluşma yordamı için bir alt küme ya da bir sorgu, alt sınır için bir sayı okumasıdır.
• KS45. Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. İkinci süpürme girdi büyüklüğü üzerinedir.
• KS46. Örnekler ortak tanımın üretecinden, tohum 20260218. İkinci tohum yoktur.
• KS47. Bir açıklığın daralması yön göstergesi sayılmaz. Daralma ölçülür, yorumlanmaz.

Sorunun Kendisi

İfade kısa ve tek anlamlıdır. P, girdi büyüklüğünün bir polinomuyla sınırlı adımda çözülen karar problemlerinin sınıfıdır. NP, “evet” yanıtı aynı sınırda doğrulanan problemlerin sınıfıdır. Her çözülen problem doğrulanabilir olduğuna göre P, NP’nin içindedir. Sorulan şey şudur: NP’nin içinde, P’de olmayan bir problem var mı.

Sorunun bir yönü kurulmuştur ve gösterilmesi kolaydır. Öteki yön iki biçimde kapanabilirdi: ya NP-tam bir problem için polinom adımlı bir yordam bulunur ve iki sınıf çakışır, ya da öyle bir problem için polinom adımın yetmediği kanıtlanır ve ayrılırlar. İkisi de yapılmamıştır ve bu ders hangisinin olacağı hakkında hiçbir şey söylemez.

Neden bir koşumun bu soruyu kapatamayacağı da açıktır. Bir yordamın 4096 adım harcaması, o problem için 4096 adımın gerektiğini göstermez; yalnız o yordamın o kadar harcadığını gösterir. Bir alt sınır kanıtı ise bütün yordamlar hakkında konuşur ve hiçbir koşum bütün yordamları tüketemez. Bu kursun aşırı iddia yasağı tam olarak bu boşluğu kapatmak içindir.

Ölçülebilen Tek Şey

Aşağıdaki blok üç sayıyı yan yana koyar: bilinen alt sınır, bu kursta kurulan en iyi yordamın adımı, ve tam taramanın adımı. Buluşma yordamının yanıtı her örnekte tam taramayla 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 tam_tarama(sayilar, hedef):
    """Bir adim = bir alt kume."""
    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 bulusma(sayilar, hedef):
    """Girdi ikiye bolunur , her yarinin butun alt kume toplamlari cikarilir
    ve ikinci yaridan sorgulanir. Bir adim = bir alt kume ya da bir sorgu."""
    n = len(sayilar)
    sol, sag = sayilar[: n // 2], sayilar[n // 2:]
    adim, tablo = 0, set()
    for maske in range(1 << len(sol)):
        adim += 1
        tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1))
    for maske in range(1 << len(sag)):
        adim += 1
        t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1)
        if hedef - t in tablo:
            return True, adim
    return False, adim


ORN = ornekler()
uyan, tt, bt, asg = 0, 0, 0, 0
for o in ORN:
    y1, a1 = tam_tarama(o["sayilar"], o["hedef"])
    y2, a2 = bulusma(o["sayilar"], o["hedef"])
    uyan += y1 == y2
    tt, bt, asg = tt + a1, bt + a2, asg + len(o["sayilar"])
print("20 ornek , n=12 | iki yordamin yaniti uyusan:", uyan, "/ 20")
print("  bilinen alt sinir:", asg, "adim | bulusma yordami:", bt,
      "adim | tam tarama:", tt, "adim")
print()
print("butce  tam tarama  bulusma yordami")
for b in (13, 100, 1000, 10000):
    c1 = sum(1 for o in ORN if tam_tarama(o["sayilar"], o["hedef"])[1] <= b)
    c2 = sum(1 for o in ORN if bulusma(o["sayilar"], o["hedef"])[1] <= b)
    print(f"{b:5d}  {c1:10d}  {c2:15d}")
print()
print(" n  alt sinir  bulusma  tam tarama  bulusma/alt sinir  tarama/alt sinir")
for n in (8, 12, 16, 20, 24):
    bul = (1 << (n - n // 2)) + (1 << (n // 2))
    print(f"{n:2d}  {n:9d}  {bul:7d}  {1 << n:10d}  {bul / n:17.1f}"
          f"  {(1 << n) / n:16.1f}")

20 ornek , n=12 | iki yordamin yaniti uyusan: 20 / 20
  bilinen alt sinir: 240 adim | bulusma yordami: 1357 adim | tam tarama: 4321 adim

butce  tam tarama  bulusma yordami
   13           0                0
  100           7               20
 1000          19               20
10000          20               20

 n  alt sinir  bulusma  tam tarama  bulusma/alt sinir  tarama/alt sinir
 8          8       32         256                4.0              32.0
12         12      128        4096               10.7             341.3
16         16      512       65536               32.0            4096.0
20         20     2048     1048576              102.4           52428.8
24         24     8192    16777216              341.3          699050.7

Açıklığın Okunması

Üç sayı yan yana: alt sınır 240, buluşma 1357, tam tarama 4321. İkinci yordam birincinin üçte birinden azını harcıyor ve 20 örneğin 20’sinde aynı yanıtı veriyor. Bu bir iyileşmedir, ölçüldü, ve gerçektir.

Bütçe süpürmesi iyileşmenin nerede işe yaradığını gösteriyor. Bütçe 100’de tam tarama 7 örnekte kalırken buluşma yordamı 20’de 20 veriyor. Bütçe 1000’de tam tarama 19’a çıkıyor, 10.000’de ikisi de dolu. Yani iyileşmenin görünür olduğu bir bütçe aralığı var ve o aralığın dışında iki yordam ayırt edilemiyor.

Girdi boyu tablosu asıl soruyu yanıtlıyor: açıklık kapanıyor mu. Buluşma sütunu 32, 128, 512, 2048, 8192; her satırda dörde katlanıyor. Tam tarama sütunu 256’dan 16.777.216’ya, her satırda on altıya katlanarak gidiyor. Alt sınıra oranlar ise 4,0’dan 341,3‘e ve 32,0’dan 699.050,7’ye çıkıyor.

Okunması gereken şey iki sütunun ikisinin de büyümesidir. İyileşme oranı azaltmadı; artış hızını azalttı. Yirmi dört sayıda buluşma yordamı tam taramadan 2048 kat ucuz, ama alt sınırdan hâlâ 341 kat pahalı. Açıklık daraldı, kapanmadı ve bu tabloda kapanacağına dair hiçbir işaret yoktur — kapanmayacağına dair de yoktur.

İyileşme İki Yönde de Var Mı

Evet kümesindeki 3,18 katlık kazanç kısmen erken durmadan geliyor olabilir: tam tarama uyan alt kümeyi bulunca duruyor ve bu, ona haksız bir avantaj değil, gerçek bir indirim sağlıyor. Kazancın yapıdan mı yoksa erken durmadan mı geldiği, erken durmanın hiç olmadığı bir kümede ölçülür. 04’ün yapısız hayır örnekleri tam olarak böyledir.

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):
    """Kurulum adimi: erisilmeyen bir hedef secilir , yanit kesin 'hayir'."""
    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 bulusma(sayilar, hedef):
    n = len(sayilar)
    sol, sag = sayilar[: n // 2], sayilar[n // 2:]
    adim, tablo = 0, set()
    for maske in range(1 << len(sol)):
        adim += 1
        tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1))
    for maske in range(1 << len(sag)):
        adim += 1
        t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1)
        if hedef - t in tablo:
            return True, adim
    return False, adim


ORN = ornekler()
EVET = [(o["sayilar"], o["hedef"]) for o in ORN]
HAYIR = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ORN]
print("kume   uyusan  tam tarama  bulusma  oran")
for ad, kume in (("evet ", EVET), ("hayir", HAYIR)):
    uyan = tt = bt = 0
    for s, h in kume:
        y1, a1 = tam_tarama(s, h)
        y2, a2 = bulusma(s, h)
        uyan += y1 == y2
        tt, bt = tt + a1, bt + a2
    print(f"{ad}  {uyan:6d}  {tt:10d}  {bt:7d}  {round(tt / bt, 2):5}")

kume   uyusan  tam tarama  bulusma  oran
evet       20        4321     1357   3.18
hayir      20       81920     2560   32.0

Hayır kümesinde iki yordam da erken duramıyor, yani ikisi de işlerinin tamamını yapıyor. Tam tarama 81.920, buluşma 2560 adım harcıyor ve oran 32,0. Bu, evet kümesindeki 3,18’in on katıdır. Sonuç şudur: kazancın kaynağı erken durma değil, yordamın yapısıdır; evet kümesindeki oranın düşük görünmesi, tam taramanın oradan bir indirim almasındandır.

Bu ayrım açık soruyla ilgilidir. Bir iyileşmenin gerçekten yapısal olup olmadığı, ancak indirimsiz bir kümede ölçülerek görülür. Buna karşın 32,0 oranı da bir yön göstermez: sabit bir çarpanla bölünen bir üstel, hâlâ bir üsteldir ve tablo bunu 24 sayıda 341 katlık uzaklıkla zaten göstermişti.

Bütçe Sabitken Ne Kadar İleri Gidilir

İyileşmenin mühendislikteki karşılığı orandan çok erişilen girdi büyüklüğüdur. Bir adım bütçesi sabitlenip her yordamın o bütçede en çok kaç sayı işleyebildiği hesaplanabilir. Aşağıdaki tablo üçüncü bir sütun daha taşır ve o sütun varsayımsaldır: karesel adımlı bir yordam bulunsaydı ne olurdu. Böyle bir yordamın var olduğu iddia edilmiyor; sütun yalnız sorunun neyi değiştireceğini gösteriyor.

def en_buyuk_n(butce, maliyet, ust=200000):
    """Butce icinde kalan en buyuk girdi buyuklugu."""
    en = 0
    for n in range(1, ust + 1):
        if maliyet(n) <= butce:
            en = n
    return en


def tarama(n):
    return 1 << n


def bulusma(n):
    return (1 << (n - n // 2)) + (1 << (n // 2))


def karesel(n):
    return n * n


print("adim butcesi     tam tarama  bulusma  varsayimsal n^2")
for b in (10 ** 4, 10 ** 6, 10 ** 8, 10 ** 10):
    print(f"{b:14d}  {en_buyuk_n(b, tarama):10d}  {en_buyuk_n(b, bulusma):7d}"
          f"  {en_buyuk_n(b, karesel):15d}")

adim butcesi     tam tarama  bulusma  varsayimsal n^2
         10000          13       24              100
       1000000          19       37             1000
     100000000          26       50            10000
   10000000000          33       64           100000

Bütçe on bin katına çıkarıldığında tam taramanın eriştiği girdi büyüklüğü 13’ten 33’e çıkıyor: bütçe on binlerce kat büyüyor, girdi büyüklüğü yirmi sayı kazanıyor. Buluşma yordamı aynı bütçelerde 24’ten 64’e gidiyor, yani her bütçede tam taramanın yaklaşık iki katı girdiye yetiyor. Bu gerçek ve ölçülmüş bir kazançtır.

Üçüncü sütun farkın niteliğini gösteriyor. Varsayımsal karesel yordam aynı bütçelerde 100’den 100.000’e çıkıyor. İlk iki sütun bütçeyi büyüterek birkaç sayı kazanıyor, üçüncüsü büyüklük düzeyi kazanıyor. P–NP sorusunun mühendislikteki karşılığı bu iki davranış arasındaki farktır: birinci ve ikinci sütun aynı ailedendir, üçüncüsü başka bir ailedendir, ve alt küme toplamı probleminin hangi ailede olduğu bilinmiyor.

Bu Dersin Söylemediği

Yukarıdaki hiçbir sayı bir yön göstermez ve gösterecek biçimde okunmamalıdır. Buluşma yordamının tam taramayı 2048 kat geçmesi, daha iyisinin bulunacağını düşündürmez; buluşma yordamının alt sınırdan 341 kat uzak kalması da bulunmayacağını düşündürmez. Ölçüm bu iki cümlenin hiçbirini destekleyecek türden bir şey değildir.

Söylenebilecek olan tam olarak şudur. Bu derste kurulan en iyi yordam 12 sayıda 1357 adım harcadı; bilinen alt sınır 240 adımdı; aradaki oran girdi büyüklüğü 24’te 341,3’e çıktı. Bu cümle ölçülmüştür ve bütçesiyle birlikte yazılmıştır. “Alt küme toplamı polinom zamanda çözülemez” cümlesi ise ölçülmemiştir, bu kursta kanıtlanmamıştır ve kimse tarafından kanıtlanmamıştır; yazılırsa kurala aykırıdır.

Aynı katılık ters yön için de geçerlidir. “Bir gün polinom bir yordam bulunacak” cümlesi de ölçülmüş değildir. Açık bir soru hakkında yazılabilecek tek dürüst cümle, sorunun açık olduğunu söyleyen cümledir.

Mühendislikte Karşılığı

Sorunun açık kalması bir mühendisi işsiz bırakmaz; tersine, ne yapılacağını netleştirir. Bir problemin NP-tam bir probleme indirgendiği biliniyorsa, o probleme genel ve ucuz bir çözüm aramak, çözülmemiş bir kuram sorusunu çözmeye çalışmakla aynı şeydir. Bu, yapılamaz demek değildir; yapılan işin ne olduğunu doğru adlandırmaktır.

Pratikte üç yol kalır ve üçü de bu kursta ölçüldü ya da ölçülecek. Birincisi girdiyi küçük tutmaktır: bütçe tablosu 12 sayıda hangi yordamın yettiğini gösterdi. İkincisi yordamı iyileştirmektir: buluşma yordamı erişilen girdi büyüklüğünu iki katına çıkardı. Üçüncüsü kesin çözümden vazgeçmektir, ve bu sonraki dersin konusudur.

Özet

• P–NP sorusu, NP sınıfının içinde P’de olmayan bir problem bulunup bulunmadığını sorar ve açıktır; bu ders hiçbir yön iddia etmez.
• Sonlu bir koşum soruyu kapatamaz, çünkü bir yordamın adımını ölçer, bütün yordamlar hakkında konuşamaz.
• Yirmi örnekte bilinen alt sınır 240, buluşma yordamı 1357, tam tarama 4321 adım; iki yordam 20 örneğin 20’sinde aynı yanıtı veriyor.
• Girdi boyu 8’den 24’e çıkarken buluşma 32’den 8192’ye, tam tarama 256’dan 16.777.216’ya gidiyor; alt sınıra oran 4,0’dan 341,3’e ve 32,0’dan 699.050,7’ye çıkıyor. Açıklık daraldı, kapanmadı.
• Bir milyon adımlık bütçede tam tarama 19, buluşma 37 sayıya yetiyor; varsayımsal karesel bir yordam 1000 sayıya yeterdi.
• Açık bir soru hakkında yazılabilecek tek dürüst cümle, ölçülmüş açıklığı bütçesiyle birlikte bildiren ve sorunun açık olduğunu söyleyen cümledir.

Sonraki Adım

Bu ders üçüncü yolu açıkta bıraktı: kesin çözümden vazgeçmek. Sonraki ders bunun bedelini sayar. Yaklaşık bir çözüm kaç örnekte kesin sonucu buluyor, bulamadığında ne kadar uzağa düşüyor, ve yaklaşık yordama verilen bütçe büyütüldüğünde kayıp gerçekten kapanıyor mu. Kursun ve M01 müfredatının son dersi bu soruyla biter.