Alt küme toplamı problemi sayfasının kaynağını görüntüle

{{Tek kaynak|tarih=Ağustos 2020}}
Bilgisayar bilimlerinde, '''alt küme toplamı problemi''' karmaşıklık kuramında ve [[kriptografi]]de ö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.

<br />
== 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 = {<math>x_1</math>, ... ,<math>x_k</math>} ve bazı Y = {<math>y_1</math>, ..., <math>y_l</math>} ⊆ S için <math>\sum_{i=1}^l y_i = t </math> }

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;
# Dilin, [[NP]] sınıfında yer aldığını,
# [[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ı, <math>SUBSET-SUM \in NP</math>, 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:<br />
<br />
V= "< < S,t >,c > girdisinde:
# Sertifikada bulunan elemanların toplamının t’ye eşit olup olmadığını test et
# Sertifikada bulunan elemanların S kümesinin elemanı olup olmadığını test et
# 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 [[Çokterimli zamanda indirgeme|polinom zamanda indirgenebilir]], <math>3SAT  \leq_p SUBSET-SUM</math>, olduğu bir tablo kullanılarak gösterilebilir.<ref>Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.</ref>

Φ; <math>x_1</math>, ..., <math>x_l</math> değişkenli, <math>c_1</math>, ..., <math>c_k</math> 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 <math>y_1</math>, <math>z_1</math>, ..., <math>y_l</math>, <math>z_l</math> ve <math>g_1</math>, <math>h_1</math>, ..., <math>g_k</math>, <math>h_k</math> 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 <math>x_i</math> değişkeni için <math>y_i</math> ve <math>z_i</math> ş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 <math>x_i</math> ∈ <math>c_j</math> ise <math>y_i</math> sayısının j’inci hanesine 1 konur.
:Eğer <math>\bar x \,</math><sub>i</sub> ∈ <math>c_j</math> ise <math>z_i</math> 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, <math>c_j</math> cümlesine uygun düşen haneye 1 rakamı, geri kalan k-j haneye ise 0 yerleştirilerek oluşturulur.

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

[[Dosya:SubsetSumTablo.jpg|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 <math>x_i</math> değişkeninin değeri TRUE ise altkümeye <math>y_i</math> sayısı
:Φ’yi doğrulayan <math>x_i</math> değişkeninin değeri FALSE ise altkümeye <math>z_i</math> 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 <math>y_i</math> ya da <math>z_i</math> 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 <math>y_i</math> sayısının ya da <math>z_i</math> 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 <math>y_i</math> sayısı bulunuyorsa <math>x_i</math> değişkenine TRUE değeri,
:Eğer alt kümede <math>z_i</math> sayısı bulunuyorsa <math>x_i</math> 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 <math>y_i</math> veya <math>z_i</math> 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ı, <math>y_i</math> sayısından geliyorsa <math>x_i</math> ∈ <math>c_j</math> ve <math>x_i</math> = TRUE
:eğer bu 1 rakamı, <math>z_i</math> sayısından geliyorsa <math>\bar x \,</math><sub>i</sub> ∈ <math>c_j</math> ve <math>x_i</math> = FALSE

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

== Ayrıca bakınız ==
* [[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 ==
{{Kaynakça}}

[[Kategori:Karmaşıklık teorisi]]
[[Kategori:Dinamik programlama]]