(2,3,4,) bunların alt kumesini yazın
(a,b,c,6,7,) alt kumesini yaz
Sertifikada bulunan eleman
3SAT Problemi, Alt Küme Toplamı Problemine Polinom Zamanda İndirgenebilir [değiştir]
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, , olduğu bir tablo kullanılarak gösterilebilir.[1]
Φ; , ... , değişkenli, , ... , 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 , , ... , , ve , , ... , , 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 değişkeni için ve ş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 ∈ ise sayısının j’inci hanesine 1 konur.Eğer i ∈ ise 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ümlesine uygun düşen haneye 1 rakamı, geri kalan k-j haneye ise 0 yerleştirilerek oluşturulur.
Aşağıdaki tablo Φ = ( 2 ) ( ... ) ( 3 ... ... )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 değişkeninin değeri TRUE ise altkümeye sayısıΦ’yi doğrulayan değişkeninin değeri FALSE ise altkümeye 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 ya da 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 sayısının ya da 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 sayısı bulunuyorsa değişkenine TRUE değeri,Eğer alt kümede sayısı bulunuyorsa 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 veya 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ı, sayısından geliyorsa ∈ ve = TRUEeğer bu 1 rakamı, sayısından geliyorsa i ∈ ve = FALSE
olduğundan dolayı Φ formülünde bulunan her 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 olarak ifade edilebilir, dolayısıyla bu indirgeme için harcanan zamanın O() olduğu söylenebilir.
İlgili bağlantılar
ları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."