3SAT-KLIK indirgemesi; Hangi düğümler birleşmiş harflerin değerinin doğruydu?
düğümler tümleyenleri ile birleşemiyorlar
Aynı zamanda, düğümler tümleyenleri ile birleşemiyorlar çünkü varsayıma göre, birleşmiş harflerin değerinin doğruydu. Bundan dolayı G çizgesi k-klik içeriyor. # G dizgesinin k-klik olduğunu varsayalım, Klik içinde olan iki düğüm kesinlikle aynı 3-lüde olamazlar çünkü aynı 3-lüde olan düğümler birbirine bağlı değil. Bundan dolayı k-klikte yer alan düğümlerin her biri farklı 3-lüde yer alır. \phi \,’nin değerin doğru atamamızdan dolayı, cümlecikteki harflerin değerlerini doğru varsaymaktır. Bundan dolayı, birbirinin tümleyeni olan düğümler bağlı değil ve aynı klikte yer alamazlar. Değişkenlerin bu gibi değerlerle atanması \phi \,'nin değerini doğru yapmış olur ve karşılanabilir olmuş oluyor. Sonuç: İlk baştaki amacımız NP sınıfında olan iki problem arasında birbirine indirgeme yapmaktı. 3SAT bir formül, diğer tarafta da Klik bir çizge olduğu halde, ispat sonucunda indirgeme sağlandı ve problemler birbirinin cinsinde gösterilebildi. .Karmaşıklık teorisi.dendir. 