Alt küme toplamı problemi; İlk satırdaki t sayısının son k hanesinde kaç rakamı vardır?
3
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 .Karmaşıklık teorisindendir. Dinamik programlama.