Alt küme toplamı problemi

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Bilgisayar bilimlerinde, alt küme toplamı problemi karmaşıklık kuramında ve kriptografide önemli yeri olan bir problemdir.

Karmaşıklık kuramında, problemin tanımı ve açıklaması basit ve anlaşılır olduğundan NP-Complete sınıfında yer alan problemleri anlayabilmek için iyi bir örnek oluşturmaktadır.

Kriptografide ise, alt küme toplamı probleminin önemli bir yer tutmasının sebebi, şifrelenmiş bir metnin anahtarını bulabilmeyi sağlamasıdır.


Problemin Tanımı[değiştir | kaynağı değiştir]

Alt küme toplamı sınıfı, alt kümeleri arasında elemanları toplamı t olan bir küme bulunan tüm S kümelerini içerir. Matematiksel olarak şöyle ifade edilir:

SUBSET-SUM = { < S,t > | S = {x_1, ... ,x_k} ve bazı Y = {y_1, ... , y_l} ⊆ S için \sum_{i=1}^l y_i = t }

Bu tanımda geçen S ve Y kümeleri multisetlerdir, bu kümelerde eleman tekrarına izin verilir.

Basit bir örnek vermek gerekirse: < {1,2,3,4}, 5 > ∈ SUBSET-SUM


Alt Küme Toplamı Probleminin Karmaşıklığı[değiştir | kaynağı değiştir]

Alt küme toplamı problemi NP-Complete sınıfında yer almaktadır. Bir dilin NP-Complete sınıfına ait olduğunu göstermek için;

  1. Dilin, NP sınıfında yer aldığını,
  2. NP sınıfında yer alan diğer tüm dillerin polinom zamanda o dile indirgenebilir olduğunu

göstermek gerekmektedir.

Alt Küme Toplamı Problemi NP Sınıfında Bulunur[değiştir | kaynağı değiştir]

Alt küme toplamı probleminin [NP] sınıfında yer aldığını, SUBSET-SUM \in NP, göstermek için bir doğrulayıcı (verifier) kullanılabilir. Sertifika olarak S’in bir alt kümesini kullanacak olan bu doğrulayıcı aşağıdaki gibi yazılabilir:

V= "< < S,t >,c > girdisinde:

  1. Sertifikada bulunan elemanların toplamının t’ye eşit olup olmadığını test et
  2. Sertifikada bulunan elemanların S kümesinin elemanı olup olmadığını test et
  3. Eğer ikisi de tamamsa, kabul et; değilse reddet."

3SAT Problemi, Alt Küme Toplamı Problemine Polinom Zamanda İndirgenebilir[değiştir | kaynağı değiştir]

NP sınıfındaki tüm dillerin polinom zamanda alt küme toplamı diline indirgenebilir olduğunu göstermek için NP-Complete olan 3SAT dili kullanılabilir.

Bu problemin alt küme toplamı problemine polinom zamanda indirgenebilir, 3SAT  \leq_p SUBSET-SUM, olduğu bir tablo kullanılarak gösterilebilir.[1]

Φ; x_1, ... , x_l değişkenli, c_1, ... , c_k cümleli (clause) Boolean bir formül olsun.

Kullanılacak olan tabloda kolonlar, Φ formülünün değişkenlerini ve cümlelerini; satırlar ise, S kümesinin elemanlarının ve t toplamının ondalık düzende gösterimlerini ifade eder.

Tablodaki çift çizginin üzerinde bulunan y_1, z_1, ... , y_l, z_l ve g_1, h_1, ... , g_k, h_k sayıları S kümesinin elemanlarıdır, çizginin alt kısmında kalan kısımda ise t sayısı yer alır. Kullanılan bu tabloda, Φ formülünde bulunan her bir x_i değişkeni için y_i ve z_i şeklinde 2 sayı yer alır . Bu sayıların ondalık gösterimi iki bölümden oluşur. Tablonun sol tarafı, değişkenin indisine uygun y ve z satırına 1 rakamı, geri kalan kısımlarına ise tabloda görüldüğü gibi l-i tane 0 yerleştirilerek oluşturulur. Tablonun sağ tarafında ise, Φ’de bulunan her bir cümle için bir hane bulunur ve şu şekilde doldurulur:

Eğer x_ic_j ise y_i sayısının j’inci hanesine 1 konur.
Eğer \bar x \,ic_j ise z_i sayısının j’inci hanesine 1 konur.

Değerinin 1 olduğu belirtilmemiş hanelere ise 0 rakamı yerleştirilir.

Yukarıda bahsedilenlere ek olarak S kümesi, Φ’de bulunan her bir cümle için g ve h sayılarını barındırır. Bu iki sayı birbirine eşittir. Bu sayılar, c_j cümlesine uygun düşen haneye 1 rakamı, geri kalan k-j haneye ise 0 yerleştirilerek oluşturulur.

Aşağıdaki tablo Φ = ( x_1 \lor \bar x \,2 \lor x_3) \land ( x_2 \lor x_3 \lor ... ) \land ( \bar x \,3 \lor ... \lor ... )için doldurulmuştur.

358 × 455px

Φ'nin doğrulanabilir (satisfiable) olduğu varsayılırsa;

Bu varsayıma göre S’in bir alt kümesi oluşturulabilir. Bu alt kümeyi oluşturmak için şöyle bir yol izlenebilir:

Φ’yi doğrulayan x_i değişkeninin değeri TRUE ise altkümeye y_i sayısı
Φ’yi doğrulayan x_i değişkeninin değeri FALSE ise altkümeye z_i sayısı

seçilir.

Oluşturulan bu alt kümenin elemanları toplandığında, tablonun t satırındaki ilk l hanede 1 rakamı elde edilir, çünkü alt kümeye ya y_i ya da z_i sayısı seçilmiştir. Ayrıca son k hanede ise toplamın en fazla 3, en az 1 olduğu görülür. Bunun sebebi, Φ formülü doğrulanabilir olduğundan her cümlede en fazla 3, en az 1 değişkenin TRUE değerini almış olmasıdır. Toplamın 3 olmadığı durumlarda ise uygun indisli g ve/veya h sayıları kullanılarak toplamın 3’e ulaşması sağlanabilir.

S kümesinin elemanları toplamı t olan bir alt kümesi olduğu varsayılırsa;

Tablodan da görüldüğü gibi, altküme elemanlarının hanelerinde ya 1 ya da 0 rakamı bulunmaktadır, ayrıca her kolonda en fazla 5 adet 1 rakamı bulunduğundan toplama işlemi eldesiz gerçekleşir. İlk l kolonda toplamın 1 olması, ya y_i sayısının ya da z_i sayısının alt küme elemanları arasında yer almakta olduğunu gösterir. İkisi birden alt kümede bulunamaz, çünkü o durumda toplamları 2 olacağından varsayıma aykırı olur. Bu varsayımdan yola çıkılarak, Φ formülünün doğrulanabilirliği şu şekilde sağlanabilir:

Eğer alt kümede y_i sayısı bulunuyorsa x_i değişkenine TRUE değeri,
Eğer alt kümede z_i sayısı bulunuyorsa x_i değişkenine FALSE değeri

atanır.

Bu atamayla Φ formülünün doğrulanabilirliği sağlanabilir, çünkü son satırdaki t sayısının son k hanesinde 3 rakamı bulunmaktadır. Son k kolonda toplamın 3 olmasını sağlayacak en az 1 tane değer, alt kümeye seçilmiş olan y_i veya z_i sayısından gelmelidir, çünkü alt kümeye seçilebilecek olan g ve h sayılarından en fazla 2 toplamı elde edilebilir.

Bu durumda;

eğer bu 1 rakamı, y_i sayısından geliyorsa x_ic_j ve x_i = TRUE
eğer bu 1 rakamı, z_i sayısından geliyorsa \bar x \,ic_j ve x_i = FALSE

olduğundan dolayı Φ formülünde bulunan her c_j cümlesi doğrulanabilir, dolayısıyla Φ formülü doğrulanabilir olduğu gösterilebilir.

Son olarak da yukarıda bahsedilen tablonun kullanımıyla yapılan bu indirgemenin polinom zamanda gerçekleştirildiğini göstermek için tablonun boyutlarına bakılabilir. Tablonun boyutları kabaca (k+l)^2 olarak ifade edilebilir, dolayısıyla bu indirgeme için harcanan zamanın O(n^2) olduğu söylenebilir.

İlgili bağlantılar[değiştir | kaynağı değiştir]

Kaynakça[değiştir | kaynağı değiştir]

  1. ^ Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.