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 = {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ığı == 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.Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005. Φ; 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. 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_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 == Kategori:Karmaşıklık teorisi Kategori:Dinamik programlama