Alt küme toplamı problemi

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ı

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 = {${\displaystyle x_{1}}$, ... ,${\displaystyle x_{k}}$} ve bazı Y = {${\displaystyle y_{1}}$, ... , ${\displaystyle y_{l}}$} ⊆ S için ${\displaystyle \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ığı

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

Alt küme toplamı probleminin [NP] sınıfında yer aldığını, ${\displaystyle 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

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, ${\displaystyle 3SAT\leq _{p}SUBSET-SUM}$, olduğu bir tablo kullanılarak gösterilebilir.^[1]

Φ; ${\displaystyle x_{1}}$, ... , ${\displaystyle x_{l}}$ değişkenli, ${\displaystyle c_{1}}$, ... , ${\displaystyle 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 ${\displaystyle y_{1}}$, ${\displaystyle z_{1}}$, ... , ${\displaystyle y_{l}}$, ${\displaystyle z_{l}}$ ve ${\displaystyle g_{1}}$, ${\displaystyle h_{1}}$, ... , ${\displaystyle g_{k}}$, ${\displaystyle 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 ${\displaystyle y_{i}}$ ve ${\displaystyle 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_i$ ∈ ${\displaystyle c_{j}}$ ise ${\displaystyle y_{i}}$ sayısının j’inci hanesine 1 konur.

Eğer ${\displaystyle {\bar {x}}\,}$_i ∈ ${\displaystyle c_{j}}$ ise ${\displaystyle 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, ${\displaystyle 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 Φ = ( ${\displaystyle x_{1}}$ ${\displaystyle \lor }$ ${\displaystyle {\bar {x}}\,}$₂ ${\displaystyle \lor }$ ${\displaystyle x_{3}}$) ${\displaystyle \land }$ ( ${\displaystyle x_{2}}$ ${\displaystyle \lor }$ ${\displaystyle x_{3}}$ ${\displaystyle \lor }$ ... ) ${\displaystyle \land }$ ( ${\displaystyle {\bar {x}}\,}$₃ ${\displaystyle \lor }$ ... ${\displaystyle \lor }$ ... )için doldurulmuştur.

Φ'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 ${\displaystyle y_{i}}$ sayısı

Φ’yi doğrulayan $x_i$ değişkeninin değeri FALSE ise altkümeye ${\displaystyle 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 ${\displaystyle y_{i}}$ ya da ${\displaystyle 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 ${\displaystyle y_{i}}$ sayısının ya da ${\displaystyle 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 ${\displaystyle y_{i}}$ sayısı bulunuyorsa $x_i$ değişkenine TRUE değeri,

Eğer alt kümede ${\displaystyle 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 ${\displaystyle y_{i}}$ veya ${\displaystyle 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ı, ${\displaystyle y_{i}}$ sayısından geliyorsa $x_i$ ∈ ${\displaystyle c_{j}}$ ve $x_i$ = TRUE

eğer bu 1 rakamı, ${\displaystyle z_{i}}$ sayısından geliyorsa ${\displaystyle {\bar {x}}\,}$_i ∈ ${\displaystyle c_{j}}$ ve $x_i$ = FALSE

olduğundan dolayı Φ formülünde bulunan her ${\displaystyle 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 ${\displaystyle (k+l)^{2}}$ olarak ifade edilebilir, dolayısıyla bu indirgeme için harcanan zamanın O(${\displaystyle n^{2}}$) olduğu söylenebilir.

İlgili bağlantılar

• Cook-Levin teoremi
• 3SAT-KLIK indirgemesi
• Bağımsız küme problemi
• Hamilton yolu problemi
• P ile NP Arasındaki İlişki
• Karmaşıklık

Kaynakça

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