Türkiye'nin ilk OldSchool MOBİL 1-99 Sunucusu Sezar2 9 Ekim'de Açılıyor! Rekor Açılışı Kaçırma! HEMEN TIKLA!
Köşe Örtme (İngilizce: Vertex Cover), bir çizge (graf) içerisindeki tüm kenarların en az sayıda seçilebilecek düğüm ile kapsanabilir olup olmadığının bulunması problemidir. Bu problemin [NP (karmaşıklık)|NP] sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin [NP (karmaşıklık)|NP-Tam] sınıfında olup olmadığının ispatıdır.
Köşe Örtme probleminin NP sınıfı içerisinde olduğu zaten görülmektedir. Çünkü NP sınıfındaki bir probleme ilişkin verilen bir çözümün polinom zamanda doğru olup olmadığını tespit etmek mümkündür. Örneğin verilen bir grafın içinde tüm kenarları kapsayan bir alt küme olduğunu iddia eden bir çözümün doğruluğu için O(n2) zaman yeterlidir. Bu çözüm için iç içe iki tane döngü içerisinde düğümler arasındaki ilişkiyi izlemek yeterlidir.
Köşe Örtme probleminin NP sınıfı içerisinde olduğu zaten görülmektedir. Çünkü NP sınıfındaki bir probleme ilişkin verilen bir çözümün polinom zamanda doğru olup olmadığını tespit etmek mümkündür. Örneğin verilen bir grafın içinde tüm kenarları kapsayan bir alt küme olduğunu iddia eden bir çözümün doğruluğu için O(n2) zaman yeterlidir. Bu çözüm için iç içe iki tane döngü içerisinde düğümler arasındaki ilişkiyi izlemek yeterlidir.