Alt küme toplamı problemi

[asdasdasddj]

ROHAN2 WORLD 1-120 TR TİPİ OFFICIAL YOHARA, BALATHOR VE AMON! 80. GÜNÜNDE! +10.000 ONLİNE! HİLE VE BOT %100 ENGELLİ HEMEN TIKLA!

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 = {x_1, ... ,x_k} ve bazı Y = {y_1, ... , y_l} &#8838; 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 > &#8712; 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= "< < 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 polinom zamanda indirgenebilir, 3SAT \leq_p SUBSET-SUM, olduğu bir tablo kullanılarak gösterilebilir.[1]

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

Kullanılacak olan tabloda kolonlar, &#934; 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, &#934; 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, &#934;’de bulunan her bir cümle için bir hane bulunur ve şu şekilde doldurulur:

Eğer x_i &#8712; c_j ise y_i sayısının j’inci hanesine 1 konur.
Eğer \bar x \,i &#8712; 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, &#934;’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 &#934; = ( 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.