IRCForumları - IRC ve mIRC Kullanıcılarının Buluşma Noktası

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 Problemi

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:

[Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...]
Örneğin [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] 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.
NP-Tam Sınıfı

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