Clique NP-Tam'dır.

İfadenin ispatına geçmeden önce izleyeceğimiz yoldan kısaca bahsedelim. Clique probleminin NP olduğunu biliyoruz ve ispatımızda bunu böyle kabul etmekteyiz. Geriye NP-Tam probleminin Clique problemine indirgenebildiğini göstermek kalıyor. Bunu da SAT problemini Clique problemine indirgeyerek ifade edeceğiz. SAT problemi nedir önce buna bir göz atalım. Ayrıca aynı şekilde NP-Tam sınıfını da aşağıdaki kısımda açıklamaktayız ve daha sonra Clique ifadesinin NP-Tam olduğunun kanıtına geçeceğiz.

SAT (Doğrulanabilirlik) probleminin ne olduğundan bahsedelim. SAT problemi verilen bir boolean ifadenin sonucunun doğru olup olmayacağıyla problemidir. Yani boolean ifadeyi doğru kılacak, boolean ifadenin değişkenlerinin bir “doğru,yanlış” kombinasyonunun oluştup oluşturmayacağıyla ilgilenir. Dolayısıyla SAT problemi aşağıdaki gibi ifade edilebilir:

${\displaystyle SAT=\left\{\langle \varnothing \rangle \vert \varnothing \,{\text{doğrulanabilir boolean ifadedir}}\right\}}$

Örneğin ${\displaystyle \varnothing =\left({\bar {x}}\land y\right)\lor \left(x\land z\right)}$ gibi herhangi bir boolean ifadenin sonucunun doğru olmasını inceleyen probleme SAT problemi denir. Bu örnekte x=doğru, y=yanlış, z= doğru için problem doğrulanabilirdir.

Bir B dili NP-tam ise şu iki şartı sağlamalıdır:

1. B dili NP sınıfındadır.
2. NP sınıfındaki her dil B diline polinom zamanda indirgenebilir.

Burada yeni bir kavramla karşılaşıyoruz; “polinom zamanda indirgemek”. Bunu fazla derine inmeden şöyle özetleyebiliriz; eğer bir problemin çözümünü bilmiyorsak ya da çözümü bulmakta çok zorlanıyorsak asıl problemimizi çözmeye yardımcı olacak yeni bir probleme indirgeriz ve çözüme yeni indirgenmiş problem aracılığıyla ulaşırız. Eğer bu indirgememiz polinom zamanda gerçekleştirilirse buna da “polinom zamanda indirgemek” adını veririz. Buna şöyle bir örnek verebiliriz: Bilmediğiniz bir yere gitmek istediğinizi farz edelim ve bu problemin sizin için zor bir problem olduğunu düşünelim. Bu durumda gideceğiniz yere ulaşmak için bir yardımcıya ihtiyacınız olacaktır. Bu yardımcılar taksiye binmek, harita elde etmek ya da bilen birine sormak bunlar arasında sayılabilir. Böylelikle bizim için zor olan problemimiz taksi ya da harita bulmak kadar basit bir probleme indirgenmiş oldu. Kısaca buna da değindikten sonra artık teoremimize dönelim.

Giriş bölümünde de bahsettiğimiz üzere artık göstermemiz gereken şey SAT probleminin k-Clique problemine indirgenebiliyor olduğudur.

Teorem: SAT, k-Clique problemine indirgenebilir.

Kanıt a :

F ifadesini boolean bir ifade olarak kabul edelim.

k=r ve G=(V,E) olarak tanımlayalım.

V={<x_i,f_j> (x_i f_j içinde bir değişken)}

E={<x_i,f_j> (<y_s,f_t> | j!=t ve <x_i != y_ş} y_ş ifadesi y_s ifadesinin tersidir.

Öncelikle F ifadesinin karşılanabilir olduğunu ispatlayalım ve sonrasında bir k-Clique elde edeceğiz.

F ifadesinin karşılanabilir olduğunu varsayalım.

Bu, F ifadesini 1'e eşitleyen bir atamanın olduğu anlamına gelmektedir.

Bu da açıklar ki F ifadesini oluşturan tüm alt f fonksiyonarı da 1'e eşitlenmiş olur.

Böylece anlarız ki her f_i ifadesinde en az bir değişkenin değeri mutlaka 1'e eşit olur.

Kanıt b :

Eğer G çizgesi bir k-Clique'e sahip ise F ifadesi karşılanabilirdir diyebiliriz.

Şimdi de G çizgesinin k-Clique içerdiğini varsayalım. <u₁,F₁>,<u₂,F₂>,.......,<u_k,F_k> değerleri birbirine komşudur.

Buna ilaveten <u_i> ve <u_j> birbirinin tersi olamaz çünkü <u_i,F_i> ve <u_j,F_j> birbirine komşu iki köşeyi göstermektedir.

Dolayısıyla artık her <u_i> değerine artık 1 değeri ataması yapabiliriz.

Bu atama her F_i değerini 1'e eşitler.

Böylece F ifadesini 1'e eşitlemiş olduk.

F=1 karşılamasını gerçekleştirdik. Böylece SAT problemini Click problemine indirgemiş olduk.

Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.