Algoritma Analizi - NP-Complete - Çözümü Bulmak Zor Ancak Doğrulamak Kolay İse

Giriş
Bir NP-Hard problem bir başka NP-Hard probleme dönüştürülebiliyorsa NP-Complete oluyor.

NP-Complete bir problemin bir başka NP-Complete probleme dönüştürülebileceği kabul edilir. Dolayısıyla NP-Complete bir çözüm bulmak diğer problemlerin de çözülmesi anlamına gelir.

Bazı Polynomial problemler NP-Complete problem olabiliyor. Örnekleri şöyle.

- 2-SAT is in P; 3-SAT is NP-complete.
- Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete
- Two-dimensional matching is in P; three-dimensional matching is NP-complete
- Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

SAT, NP-Complete olarak sınıflandırılan ilk problem. Açıklaması şöyle

SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of SAT.

Set Cover Problemi - Küme Örtme Problemi
Set Cover problemleri NP Complete problemlerdir. Set Cover problemi elimizde bir çok set olduğunu, bu setlerin hepsinin birleşiminin (union) evrensel seti oluşturduğunu varsayar. Evrensel seti oluşturmak için kullanılacak en az sayıdaki seti bulma problemidir. Kümelerimiz şunlar olsun

S1 = {2,3}
S2 = {2, 5}
S3 = {4, 5}
S4 = {4}
S5 = {5}

Evrensel kümemiz şudur
S {2, 3, 4, 5}.

S1, S3 kümeleri (2 küme) ile evrensel kümeye erişebilirim. Aynı zamanda S1, S4, S5 (3 küme) ile de erişebilirdim ama sayısı 3 olduğu için seçmiyorum. Gerçek hayatta şöyle bir örnek verilebilir.
Bir ilçenin 5 mahallesi olsun. Her mahalleye sağlık hizmeti götürmek isteniyor. Kurulacak sağlık ocağı her mahalleye en fazla 20 dakika mesafede olsun da isteniyor. Tüm mahallelerine hizmet verecek en az sayıda kaç sağlık ocağı kurabilirim.
Probleme yukarıdaki gibi kümeler oluşturularak başlanır.

S. Ocak1 = {Mahalle2,Mahalle3}
S. Ocak2 = {Mahalle2,Mahalle5}
S. Ocak3 = {Mahalle4,Mahalle5}
S. Ocak4 = {Mahalle4}
S. Ocak5 = {Mahalle5}

Evrensel kümemiz {Mahalle2, Mahalle3, Mahalle4, Mahalle5} 'tir.
Tüm mahallelere hizmet vermek için S.Ocak1, S.Ocak2, S.Ocak3 yeterlidir.

Diğer bir Örnek
Başka bir NP problem örneği

S kümesini A ve B olarak iki alt kümeye ayır. A ve B'deki elemanların toplamı eşit olsun. 

Bu problemin kolay bir çözümü yok. Muhtemelen tüm olasılıkları denemek gerekiyor. Ancak bize A ve B kümeleri hazır verilseydi sonucu kolayca doğrulayabilirdik.

Degree Constrained Minimum Spanning Tree
Degree Constrained Spanning Tree NP Complete problemlerdir.

Edge matching problems

Açıklaması şöyle

Edge matching problems, such as the Eternity II puzzle are NP-complete

Hamiltonian Path

Açıklaması şöyle. 

... start with any node, then go through each other node exactly once, and then go back to the beginning, so it means the path is actually a cycle. A path that goes through all nodes exactly once called a Hamiltonian path. Consequently, such a cycle is a Hamiltonian cycle.

Eğer Hamiltonian Path kullanırken bazı kısıtlar varsa, ve bu kısıtlar yüzünden döngü tamamlanamıyorsa,  backtracking search veya depth-first search kullanılabilir. Açıklaması şöyle

At some steps, we can find out that there are no available nodes to pick. It might happen if there are no more connections (because of constraints) or if all neighbor nodes have been visited already. This issue looks like the issue we had with the naive algorithm. With a graph, it’s more clear that we can do a step back and pick another random node. If we did a step back and there are still no nodes to pick, we do another step back.

Repeat until we visit all nodes and return to the first one. The cycle is complete.

Such a search is called backtracking search or depth-first search.

Çözümü Doğrulamak
Çözümü doğrulamak için ilave bilgi gerekebilir. Açıklaması şöyle.

Also note that "checking" does not always just mean "here's an answer, go check it." When one is checking a NP-complete answer, one is typically given extra information derived from the solving of the problem. My favorite example is proving that a number is prime. One can provide a list of "witness" integers which, together, can prove that a number is prime. Finding the correct list of numbers is very difficult, but once you have the list, the verification is trivial.