--- title: 'P Sınıfı' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/p-sinifi' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:29+00:00' license: 'CC BY-SA 4.0' --- # P Sınıfı Polinom zamanda çözülebilir karar problemlerinin, sonlu bir adım bütçesi altında ölçülmesi: aynı 20 örnekte eşik problemi 12 adımda, ikili problemi 66 adımda karara bağlanıyor, alt küme toplamı ise 10.000 adım bütçesi gerektiriyor. Girdi boyu 8'den 20'ye çıkarken ilk iki yordamın en kötü adımı 8'den 20'ye ve 28'den 190'a giderken üçüncüsü 256'dan 1.048.576'ya çıkıyor. Karar problemi sınıfının, Algoritmalar kursundaki büyüme sınıfından farkı ayrıca yazılıyor. 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. ```python 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. ```python 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. ```python 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.