| |
|
06 Nisan 2012, 10:24
| #1 | |
| Çevrimdışı  IF Ticaret Sayısı: (0) | Clique NP 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: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. Örneğin Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. 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: | |
| |  |
| IRCForumlari.NET Reklamlar |
   |
 |
| Etiketler |
| clique, np |
| Konuyu Toplam 1 Üye okuyor. (0 Kayıtlı üye ve 1 Misafir) | |
| |
Benzer Konular | ||||
| Konu | Konuyu Başlatan | Forum | Cevaplar | Son Mesaj |
| Guzel Kizlar Kulubu - The Clique 2008 - IRCForumları Sinema Kulübü | Sevda | Sinema Dünyası | 1 | 02 Şubat 2012 16:53 |
Normal
