Alt küme toplamı problemi
Alt Küme Toplamı Probleminin Karmaşıklığı > 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:
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.
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:
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.
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:
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;
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.