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 = {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:  ∈ 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ı, 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= ",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 polinom zamanda indirgenebilir, 3SAT  \leq_p SUBSET-SUM, olduğu bir tablo kullanılarak gösterilebilir.

Φ; 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_i ∈ c_j ise y_i sayısının j’inci hanesine 1 konur.
:Eğer \bar x \,i ∈ c_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.

:: **Φ'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_i ∈ c_j ve x_i = TRUE
:eğer bu 1 rakamı, z_i sayısından geliyorsa \bar x \,i ∈ c_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.

## 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