| |
|
06 Nisan 2012, 10:24
| #1 | |
| Çevrimdışı  IF Ticaret Sayısı: (0) | SAT Problemi SAT problemi bir NP-tam sınıfı problemidir. Teoremin ispatına geçmeden önce teoremin çıkış noktası üzerinde duralım. Polinom zamanda kararlaştırılan problem(P sınıfı problemleri) ile polinom zamanda doğrulanabilen problem (NP sınıfı problemleri) sınıflarının birbirine denk olup olmadığı güncel matematik ve teorik bilgisayar biliminin bir türlü çözemediği bir sorun olagelmiştir. Eğer bu sınıflar birbirine denk olduğu gösterilirse herhangi polinom zamanda doğrulanabilen bir problemin (NP sınıfı problemi) artık polinom zamanda kararlaştırılabiliyor olacağı kesin olarak söylenmiş olacaktır. 1970’lerde P ve NP sınıflarının arasındaki ilişkiye Stephen Cook ve Leonid Levin adındaki iki bilim adamı farklı bir açıdan yaklaşmışlardır; bazı NP sınıfı problemlerinin karmaşıklıklarının tek başlarına tüm NP sınıfının karmaşıklığına eşit olduğunu fark etmişler.Eğer bu tip problemlerin polinom zamanda bir çözümü bulunursa NP sınıfındaki tüm problemler polinom zamanda çözülebilir.Bu tip problemlere ilerde değineceğiz ve bun tip problemlere NP-tam sınıfı problemleri diyeceğiz. Dolayısıyla Cook-Levin yaklaşımının bir sonucu olarak P sınıfıyla NP sınıfının eşitliğini iddia eden biri NP-tam bir problemi polinom zamanda çözmesi iddiasını ispatlamak için yeterli olacaktır. 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 |
| problemi, sat |
| Konuyu Toplam 1 Üye okuyor. (0 Kayıtlı üye ve 1 Misafir) | |
| |
Benzer Konular | ||||
| Konu | Konuyu Başlatan | Forum | Cevaplar | Son Mesaj |
| Gaz Problemi | Liaaa | Sağlık Köşesi | 0 | 11 Şubat 2012 14:01 |
| tr.l problemi | Cihandar | IRCServices | 1 | 20 Ağustos 2009 00:03 |
| lag problemi | kurugaddere | mIRC Scripting Sorunları | 3 | 01 Ocak 2009 00:25 |
| +b Problemi.. | KuRSuN | Eggdrop, NeoStats, BNC | 7 | 11 Ekim 2008 18:24 |
| Kod Problemi. | SoaD | PHP | 5 | 21 Nisan 2008 18:22 |
Normal
