P Sınıfı

Hesaplama Modelleri konusu, bir sorunun yanıtlanıp yanıtlanamayacağını sordu ve sonlu bir bütçenin o soruyu her zaman kapatamadığını ölçtü. Karmaşıklık Sınıfları konusu daha dar bir alanda çalışır: yanıtı bulunabilen problemler arasında, bulmanın bedelinin girdiyle nasıl büyüdüğünü sorar. İlk soru şudur: bir problemi ucuz kılan nedir, ve ucuzluk problemin özelliği midir yoksa seçilen yordamın mı.

Bu ders üç karar problemini aynı girdi üzerinde aynı bütçeyle koşturur. İki tanesi bütçeyi neredeyse hiç zorlamıyor, üçüncüsü bütçeyi büyütmeyi gerektiriyor. Ölçülen şey hangisinin “hızlı” olduğu değil, bütçenin hangisini karara bağladığıdır.

• KS1. Bu konudaki bütün problemler karar problemidir: yanıt tek bir sözcüktür, “evet” ya da “hayır”. Karar problemi kavramı M01/K07 İleri Algoritmalar kursunda kuruldu ve burada tekrarlanmaz.
• KS2. Girdi boyu n, örnekteki sayı adedidir. Sayılar 3 ile 99 arasında tutulur, yani bir sayının basamak sayısı sabittir ve girdi büyüklüğü yalnız n ile değişir.
• KS3. Ölçü adımdır, süre değil. Bir adımın ne olduğu her yordamda ayrıca tanımlanır ve o tanım ders boyunca değişmez.
• KS4. Bütçe bir adım bütçesidir. Yordam bütçeyi tüketirse yanıt vermez; “karara bağlanmadı” döner. Bu, yanıtın olmadığı anlamına gelmez, bu bütçede kurulamadığı anlamına gelir.
• KS5. Örnekler ortak tanımın üretecinden gelir: tohum 20260218, 20 örnek, örnek başına 12 sayı. Bu kursta ikinci tohum yoktur; yerine bütçe süpürmesi vardır.
• KS6. Üç problem şunlardır. Eşik: sayıların toplamı hedefi aşıyor mu. İkili: iki sayının toplamı hedefe tam eşit mi. Alt küme toplamı: herhangi bir alt kümenin toplamı hedefe tam eşit mi.
• KS7. Bütçe süpürmesi zorunludur. Her sonuç en az üç bütçe değerinde gösterilir ve bütçeyle değişip değişmediği yazılır.
• KS8. Bir yordamın gözlenen adımı ile en kötü durumdaki adımı ayrı yazılır. İkisini karıştırmak bu dersin ölçtüğü farkı yok eder.
• KS9. Bir problemin P sınıfına ait olup olmadığı ölçülmez. Ölçülen tek şey, belirli bir yordamın adım sayısının girdi büyüklüğüyle nasıl büyüdüğüdür.
• KS10. Sabit çarpanlar elenmez. Ölçüm asimptotik değil, sayılan adımdır.

Karar Problemi Sınıfı ile Büyüme Sınıfı

M01/K04 Algoritmalar kursundaki “Karmaşıklık Sınıflarını Okumak” dersi de “karmaşıklık sınıfı” terimini kullanıyordu, ama ayrı bir şeyi adlandırıyordu. Fark tek bir cümleyle yazılabilir: orada bir sınıf tek bir yordamın maliyet ifadesini gruplar — $O(n^2)$, iç içe iki döngünün büyüme biçimidir — burada bir sınıf, hakkında yordam aranan problemleri gruplar.

Ayrımın pratik sonucu şudur. Bir yordam her zaman bir büyüme sınıfına aittir; bu, koda bakılarak belirlenir. Bir problem ise ancak “böyle bir yordamın var olduğu” gösterilerek bir karar problemi sınıfına sokulabilir, ve bu bir varlık iddiasıdır. Kod ölçülür, varlık iddiası ölçülmez.

P, bir karar problemi sınıfıdır: girdi büyüklüğünün bir polinomuyla sınırlı adımda kesin yanıt veren belirlenimci bir yordamın bulunduğu problemler. Tanımdaki üç sözcük de yüklüdür. “Polinom” bir büyüme sınırıdır; “kesin” yaklaşık çözümü dışarıda bırakır; “bulunduğu” bir varlık iddiasıdır ve tek bir koşumla kurulamaz.

Üç Karar Problemi, Bir Adım Bütçesi

Aşağıdaki blok üç problemi aynı 20 örnek üzerinde koşturur. Her yordam bir adım bütçesi alır ve bütçe dolduğunda None döndürerek karara varamadığını bildirir.

TOHUM = 20260218


def ornekler(tohum=TOHUM, n=12, sayi=20):
    """Ortak tanimin ornek ureteci: her ornek n sayi ve bir hedef."""
    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, butce):
    """Toplam hedefi asiyor mu. Bir adim = bir toplama."""
    toplam, adim = 0, 0
    for s in sayilar:
        if adim >= butce:
            return None, adim
        toplam += s
        adim += 1
    return toplam > hedef, adim


def ikili(sayilar, hedef, butce):
    """Iki sayinin toplami hedefe esit mi. Bir adim = bir ikili."""
    adim, n = 0, len(sayilar)
    for i in range(n):
        for j in range(i + 1, n):
            if adim >= butce:
                return None, adim
            adim += 1
            if sayilar[i] + sayilar[j] == hedef:
                return True, adim
    return False, adim


def alt_kume(sayilar, hedef, butce):
    """Bir alt kumenin toplami hedefe esit mi. Bir adim = bir alt kume."""
    adim, n = 0, len(sayilar)
    for maske in range(1 << n):
        if adim >= butce:
            return None, adim
        adim += 1
        if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef:
            return True, adim
    return False, adim


ORN = ornekler()
print("butce  yordam    karara baglanan  baglanmayan  en cok adim")
for b in (12, 100, 1000, 10000):
    for ad, f in (("esik    ", esik), ("ikili   ", ikili),
                  ("alt kume", alt_kume)):
        cevap = ust = 0
        for o in ORN:
            y, a = f(o["sayilar"], o["hedef"], b)
            if y is not None:
                cevap += 1
                ust = max(ust, a)
        print(f"{b:5d}  {ad}  {cevap:15d}  {20 - cevap:11d}  {ust:11d}")

butce  yordam    karara baglanan  baglanmayan  en cok adim
   12  esik                   20            0           12
   12  ikili                   0           20            0
   12  alt kume                0           20            0
  100  esik                   20            0           12
  100  ikili                  20            0           66
  100  alt kume                7           13           98
 1000  esik                   20            0           12
 1000  ikili                  20            0           66
 1000  alt kume               19            1          354
10000  esik                   20            0           12
10000  ikili                  20            0           66
10000  alt kume               20            0         1047

Bütçenin Yanıtladığı ve Yanıtlayamadığı

Üç sayı yan yana konur. Bütçe 12: eşik problemi 20 örneğin 20’sini karara bağlıyor, öteki iki problem hiçbirini. Bütçe 100: ikili problemi de 20’de 20’ye çıkıyor ve en çok 66 adım harcıyor; alt küme toplamı 7 örnekte kalıyor, 13 örnek karara bağlanmıyor. Bütçe 10.000: üçü de 20’de 20.

Bütçe süpürmesinin okunması burada iki ayrı sonuç veriyor. Eşik ve ikili problemleri için bütçeyi 100’den 10.000’e çıkarmak hiçbir şeyi değiştirmiyor: en çok adım 12 ve 66’da sabit kalıyor, çünkü bu iki yordam girdiyi zaten tüketmiş durumda. Alt küme toplamı için ise bütçe büyütmek her şeyi değiştiriyor: 7, sonra 19, sonra 20. Bu kursun ikinci iddiası tek bir tabloda iki kez görünüyor.

Sabit kalan sayıların anlamı, kalmayanlardan daha önemlidir. Eşik yordamının 12 adımı, girdide 12 sayı olduğu içindir; ikili yordamının 66 adımı, 12 sayının 66 ikilisi olduğu içindir. İkisi de girdinin kendisinden okunabilen sayılardır ve örneğe bakmadan önceden yazılabilir. Alt küme toplamının 98, 354, 1047 adımları ise önceden yazılamaz; hangi maskede duracağı örneğe bağlıdır.

Girdi Boyu Büyüyünce

Bir bütçe değerinde alınan sonuç, girdi büyüklüğü değiştiğinde ayakta kalmayabilir. İkinci süpürme girdi büyüklüğünu 8’den 20’ye çıkarır ve her yordam için en kötü durumdaki adım sayısını gözlenen en yüksek adımın yanına koyar.

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(sayilar, hedef):
    """Butun alt kumeler; ilk uyanda durur. 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


print(" n  esik  ikili  alt kume (en kotu)  alt kume (gozlenen en cok)")
for n in (8, 12, 16, 20):
    ust = max(alt_kume(o["sayilar"], o["hedef"])[1] for o in ornekler(n=n))
    print(f"{n:2d}  {n:4d}  {n * (n - 1) // 2:5d}  {1 << n:18d}  {ust:26d}")

 n  esik  ikili  alt kume (en kotu)  alt kume (gozlenen en cok)
 8     8     28                 256                         256
12    12     66                4096                        1047
16    16    120               65536                         945
20    20    190             1048576                        2684

Eşik sütunu 8, 12, 16, 20; girdi büyüklüğüyle birebir. İkili sütunu 28, 66, 120, 190; girdi büyüklüğü iki buçuk katına çıkarken adım yaklaşık yedi katına çıkıyor, yani karesel bir artış. Alt küme sütununun en kötü durumu 256’dan 1.048.576’ya gidiyor: her yeni sayı, taranacak alt küme sayısını ikiye katlıyor.

Son sütun bir tuzağı açığa çıkarıyor. Gözlenen en yüksek adım 12 sayıda 1047, 16 sayıda 945, 20 sayıda 2684. Yani gözlenen değer girdi büyüklüğüyle düzenli artmıyor, hatta 12’den 16’ya inerken azalıyor. Bunun nedeni yordamın uyan ilk alt kümede durmasıdır; bu örneklerde uyan bir alt küme erken bulunuyor. Sekiz sayılık satırda gözlenen değer en kötü durumla çakışıyor — 256’ya 256 — çünkü o dağarcıkta hiçbir alt kümenin uymadığı bir örnek var ve orada tarama sonuna kadar gidiyor.

Buradan çıkan kural şudur: gözlenen adım, bir yordamın bedeli değildir. Yirmi örnekte gözlenen en yüksek değerin 2684 olması, yirmi birinci örneğin 2684 adımda biteceğini söylemez. Bir yordamın bedelini yazmak, gözlenen bir sayıyı değil, her girdi için geçerli bir sınırı yazmaktır.

Girdi Boyu Neyle Ölçülür

P tanımındaki “polinom”, girdi büyüklüğünün polinomudur. O halde girdi büyüklüğünün ne olduğu tanımın parçasıdır, ve bu noktada dikkatsizlik sessiz bir hataya dönüşür. Alt küme toplamı için tam taramadan başka bir yordam daha vardır: erişilebilen toplamların tablosu tutulur ve her sayı tabloyu bir kez günceller. Bu yordam n çarpı hedef adım harcar, yani 12 sayı ve 180 hedef için yaklaşık 2160 adım — 4096’nın altında. Görünüşte polinom bir yordamdır.

Aşağıdaki blok bu görünüşü sınar. Bütün sayılar ve hedef aynı çarpanla büyütülür; sayı adedi değişmez, yalnız her sayının basamak sayısı artar.

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 dinamik(sayilar, hedef):
    """Erisilen toplamlar tablosu. Bir adim = bir tablo hucresi."""
    ulasilan = [False] * (hedef + 1)
    ulasilan[0] = True
    adim = 0
    for s in sayilar:
        for t in range(hedef, s - 1, -1):
            adim += 1
            if ulasilan[t - s]:
                ulasilan[t] = True
    return ulasilan[hedef], adim


print("carpan  basamak  uyusan  tam tarama adimi  dinamik adimi")
for c in (1, 10, 100):
    uyan, ta, da = 0, 0, 0
    basamak = 0
    for o in ornekler():
        s = [x * c for x in o["sayilar"]]
        h = o["hedef"] * c
        basamak = max(basamak, len(str(h)))
        y1, a1 = tam_tarama(s, h)
        y2, a2 = dinamik(s, h)
        uyan += y1 == y2
        ta, da = ta + a1, da + a2
    print(f"{c:6d}  {basamak:7d}  {uyan:6d}  {ta:16d}  {da:13d}")

carpan  basamak  uyusan  tam tarama adimi  dinamik adimi
     1        3      20              4321          37994
    10        4      20              4321         377780
   100        5      20              4321        3775640

İki yordam 20 örneğin 20’sinde aynı yanıtı veriyor, yani tablo yordamı doğru çalışıyor. Ama adım sütunları ters yönlere gidiyor. Sayılar on katına çıkarıldığında tam taramanın adımı 4321’de sabit kalıyor; tablo yordamının adımı 37.994’ten 377.780’e, sonra 3.775.640’a çıkıyor. Girdiye eklenen şey tek bir basamaktır ve sayı adedi hiç değişmemiştir.

Sonuç şudur: tablo yordamı, hedefin değerinin polinomudur, hedefi yazmak için gereken basamak sayısının değil. Bir sayıyı yazmak için gereken yer basamak sayısı kadardır, değeri kadar değil; bu yüzden girdi büyüklüğü bu yordam için üstel olarak büyür. Girdi boyu “sayı adedi” diye okunursa yordam polinom görünür, “yazılan basamak adedi” diye okunursa görünmez. Bu ders girdi büyüklüğünu KS2’de sabit basamakla tanımladığı için ilk satır dürüsttür; çarpan büyütüldüğünde o tanım bozulur ve tablo hemen bunu gösterir.

P Sınıfı Ne Söyler, Ne Söylemez

Yukarıdaki iki tablo eşik ve ikili problemlerini P sınıfına sokmaz. Sokan şey ölçüm değil, yordamın yapısıdır: eşik yordamı her girdide tam olarak n adım, ikili yordamı en çok n(n-1)/2 adım harcar ve bu iki sınır girdiye bakılmadan gösterilebilir. Ölçüm bu gösterimi sınar, yerine geçmez.

Ters yön daha da katıdır. Alt küme toplamı probleminin 20 sayıda 1.048.576 adım istemesi, bu problemin P sınıfında olmadığını göstermez. Gösterdiği tek şey, burada kurulan yordamın bu kadar adım harcadığıdır. Aynı problem için başka bir yordam bulunmadığı ölçülmedi; yalnız bu derste kurulmadı. Bu kursun kuralı bunu bir cümleye bağlar: bütçesi yazılmayan “çözülemez” iddiası ölçülmemiş sayılır.

Mühendislik karşılığı doğrudandır. Bir raporda “bu problem polinom zamanda çözülüyor” cümlesi, yanına o polinomu ve bir sınır gerekçesi ister. “Bizim yordamımız 20 örnekte 66 adımda bitiyor” cümlesi ise ölçülmüş, doğru ve çok daha zayıf bir iddiadır. İkisi aynı cümlede yazılmaz.

Özet

• Karar problemi sınıfı ile büyüme sınıfı ayrı şeylerdir: biri problemleri, öteki tek bir yordamın maliyet ifadesini gruplar.
• Aynı 20 örnekte eşik problemi 12, ikili problemi 66 adımda karara bağlanıyor; alt küme toplamı 100 adım bütçesinde 20 örneğin yalnız 7’sini bağlıyor ve 10.000’de tamamlanıyor.
• Bütçeyi 100’den 10.000’e çıkarmak ilk iki problemde hiçbir şeyi değiştirmiyor, üçüncüsünde yanıtlanan örnek sayısını 7’den 20’ye taşıyor.
• Girdi boyu 8’den 20’ye çıkarken en kötü adım sayısı 8’den 20’ye, 28’den 190’a ve 256’dan 1.048.576’ya gidiyor.
• Gözlenen adım bir yordamın bedeli değildir: 12 sayıda 1047 gözlenirken 16 sayıda 945 gözleniyor, çünkü yordam uyan ilk alt kümede duruyor.
• Bir problemin P sınıfına ait olduğu ölçülerek gösterilmez; ölçüm yalnız gösterilmiş bir sınırı sınar.

Sonraki Adım

Alt küme toplamı probleminde tarama pahalıydı, ama tarama bitince elde bir şey daha kalıyordu: hedefe toplanan alt kümenin kendisi. O alt küme bir kez elde edildiğinde, doğru olduğunu görmek için taramayı yeniden yapmak gerekmiyor. Sonraki ders bu gözlemi ölçüye çevirir: bir yanıtı bulmak ile verilmiş bir yanıtı doğrulamak arasındaki adım farkı ne kadar, ve bu farkın bir sınıf adı olması ne anlama geliyor.