3SAT ve KLIK problemleri, Turing makinasından polinom zamanda kararlaştırılabilen NP problemleri arasında yer alır. Bu problemlerin birbirinin cinsine çevrilmesine indirgeme denilir. Giriş İndirgeme: A problemi B problemine indirgenebiliyorsa, B problemin çözümü A’nın çözümü için kullanılabilir. Karmaşıklık, parçaları ve onların düzeni kavraması zor olan bir sistemdir. Karmaşıklık Kuramı sırasında ise, çözümleri zor olan problemerlerin birbirine indirgeyerk çözümlerini kolaylaştırılmaya çalışılıyor. Bununla ilgili olan P =? NP sorusunun cevabı da, aynı şekilde ilk başta problemleri indirgeyerek basitleştirmeye çalışılır, sonra da çözümleri olan problemleri kullanarak daha karmaşık olanların çözümlerine bakılır. Bu şekilde P ve NP sınıflarındaki problemleri arasında bir ilişki bulunursa, çözüme doğru gidebiliriz. NP sınınfında problemlerini çözmek için de, aynı şekilde indirgemeye başvurulur ama bu defa Polinom zamanda indirgeme olur. Polinom Zamanda İndirgeme A dili B diline polinom zamanda indirgenebilir , ancak ve ancak diye polinom zamanda çalışan bir hesaplama funksiyonu varsa ve her için geçerlidir. Dosya
olinom_zamanda_funksiyon.png 3SAT ve Klik problemlerin Karmaşıklık Sınıflarındaki yeri Dosya
iller_sınıfı.png NP sıfında yer alan problemler arasında 3SAT ve Klik problemleri de bulunur. Okla gösterildiği gibi, 3SAT ve Klik arasında indirgeme işlemi yapılacak. 3SAT problemi, SAT karşılanabilir (satisfiable) proleminin cümlecikleri 3 harften oluşmuş özel bir halidir. Dosya:6n-graf-clique.svg Resimde görüldüğü gibi, {1,2,5} düğümler arasında klik oluyor. İspat fikri Problemlerin tanımlarından da yola çıkarak 3SAT problemin bir formül, KLİK probleminin de bir çizge olduğunu fark ettik. Problemleri indirgemek ve çözümlemek için ilk başta birbirinin formatına gösterilmeleri ve çevirilmeleri gerekiyor. Örnek.1’den görüldüğü gibi, 3SAT cümlcikleri “ve” bağlacıyla bağlanmıs ve her cümlesi “veya” bağlacıyla bağlanmış 3 harften oluşuyor. Klik problemi ise, resimde gösterildiği gibi bir çizgenin içinde, birbirine bağlanan düğümlerle ilgilidir. Bu iki problemi birbirine dönüştürmenin (indirgemenin) yolu, formülü çizge gibi, çizgeyi de formül haline dönüştürmekten geçer. Belirli çizgelerin içinde k-büyüklükteki klikleri, belirli karşılanabilir formüllerle uyuşuyor. Sürülen bu fikirler üzerinden yola çıkarak, NP sınınfında olan iki problemin arasında, birbirinin cinsine taklitini kullanarak polinom zamanda indirgemeyi başarmaya çalışacağız. İspat , k cümlecikten oluşan bir formül olsun. indirgemesinin sonucu olarak, yönsüz çizge olmak üzere katarı üretilmesi bekleniyor. Bunun yapısı şöyle; Çizgedeki düğümler, aralarında 3-lü olacak şekilde gruplanıyor ve sırayla . Her bir 3-lü formüldeki bir cümleciğe, her bir düğüm de cümlecikteki bir harfe denk geliyor. Dolayısıyla G çizgesideki her düğüm ’nın bir literaline karşılık gelir. Bu çevirmeyi yaparken, förmülde “ve”, “veya” bağlaçları göz önüne alarak, çizgedeki düğümler arasında alttaki kurallar uygulanması gerekiyor. Aynı 3-lü grup içinde yer alan düğümler arasında bağlantı yok. Birbirinin tümleyeni olan iki düğüm arasında bağlantı yok, ör, x ve x'. Şu ana kadar indirgemenin zeminini hazırlamaya çalıştık, bundan sonra problemleri çevirmeye çalışacağız. Aşağıda, karşılanabilir bir örnek funksiyonu verilmiştir. Belirlenen kurallar çerçevesinde formülden çizgeye dönüşüme başlarsak, alttaki G çizgeyi elde etmiş olacağız. Dosya:Grafsat.jpg İndirgemeyi açıkça bir şekilde gördükten sonra, yöntemin tutarlığını ispatlamak için iki tane varsayım üzerinde yorum yapılacak: ’nin karşılanabilir (satisfying) olduğunu varsayalım; Son değerin doğru olduğuna göre, her cümlecikte en azında bir tane harfin değeri doğru (1) olması gerekiyor ki, “ve” işleminin sonucu olarak 1 elde edilsin. G dizgesinde her üçlü için doğru değerli harfi temsil eden bir düğüm seçiliyor. Eğer bir cümlecikte birden fazla doğru değerli harf varsa, keyfi olarak doğru olanlar aradında bir tane seçiliyor. Seçilen düğümler k-klik şeklini oluşturuyorlar. Dikkatli bakarsak, her (sayısı k olan) cümlecikten birer harf aldığımızdan dolayı seçili düğüm sayısı k’dır. K-klik içindeki düğümler aynı 3-lü gruptan olamazlar çünkü her 3-lü den sadece bir tane düğüm seçmiş olduk. Aynı zamanda, düğümler tümleyenleri ile birleşemiyorlar çünkü varsayıma göre, birleşmiş harflerin değerinin doğruydu. Bundan dolayı G çizgesi k-klik içeriyor. G dizgesinin k-klik olduğunu varsayalım; Klik içinde olan iki düğüm kesinlikle aynı 3-lüde olamazlar çünkü aynı 3-lüde olan düğümler birbirine bağlı değil. Bundan dolayı k-klikte yer alan düğümlerin her biri farklı 3-lüde yer alır. ’nin değerin doğru atamamızdan dolayı, cümlecikteki harflerin değerlerini doğru varsaymaktır. Bundan dolayı, birbirinin tümleyeni olan düğümler bağlı değil ve aynı klikte yer alamazlar. Değişkenlerin bu gibi değerlerle atanması 'nin değerini doğru yapmış olur ve karşılanabilir olmuş oluyor. Sonuç İlk baştaki amacımız NP sınıfında olan iki problem arasında birbirine indirgeme yapmaktı. 3SAT bir formül, diğer tarafta da Klik bir çizge olduğu halde, ispat sonucunda indirgeme sağlandı ve problemler birbirinin cinsinde gösterilebildi. Kaynakça Michael Sipser, Introduction to the theory of computation 2nd edition, pg.274 Kategori:Karmaşıklık teorisi
olinom_zamanda_funksiyon.png 3SAT ve Klik problemlerin Karmaşıklık Sınıflarındaki yeri Dosyailler_sınıfı.png NP sıfında yer alan problemler arasında 3SAT ve Klik problemleri de bulunur. Okla gösterildiği gibi, 3SAT ve Klik arasında indirgeme işlemi yapılacak. 3SAT problemi, SAT karşılanabilir (satisfiable) proleminin cümlecikleri 3 harften oluşmuş özel bir halidir. Dosya:6n-graf-clique.svg Resimde görüldüğü gibi, {1,2,5} düğümler arasında klik oluyor. İspat fikri Problemlerin tanımlarından da yola çıkarak 3SAT problemin bir formül, KLİK probleminin de bir çizge olduğunu fark ettik. Problemleri indirgemek ve çözümlemek için ilk başta birbirinin formatına gösterilmeleri ve çevirilmeleri gerekiyor. Örnek.1’den görüldüğü gibi, 3SAT cümlcikleri “ve” bağlacıyla bağlanmıs ve her cümlesi “veya” bağlacıyla bağlanmış 3 harften oluşuyor. Klik problemi ise, resimde gösterildiği gibi bir çizgenin içinde, birbirine bağlanan düğümlerle ilgilidir. Bu iki problemi birbirine dönüştürmenin (indirgemenin) yolu, formülü çizge gibi, çizgeyi de formül haline dönüştürmekten geçer. Belirli çizgelerin içinde k-büyüklükteki klikleri, belirli karşılanabilir formüllerle uyuşuyor. Sürülen bu fikirler üzerinden yola çıkarak, NP sınınfında olan iki problemin arasında, birbirinin cinsine taklitini kullanarak polinom zamanda indirgemeyi başarmaya çalışacağız. İspat , k cümlecikten oluşan bir formül olsun. indirgemesinin sonucu olarak, yönsüz çizge olmak üzere katarı üretilmesi bekleniyor. Bunun yapısı şöyle; Çizgedeki düğümler, aralarında 3-lü olacak şekilde gruplanıyor ve sırayla . Her bir 3-lü formüldeki bir cümleciğe, her bir düğüm de cümlecikteki bir harfe denk geliyor. Dolayısıyla G çizgesideki her düğüm ’nın bir literaline karşılık gelir. Bu çevirmeyi yaparken, förmülde “ve”, “veya” bağlaçları göz önüne alarak, çizgedeki düğümler arasında alttaki kurallar uygulanması gerekiyor. Aynı 3-lü grup içinde yer alan düğümler arasında bağlantı yok. Birbirinin tümleyeni olan iki düğüm arasında bağlantı yok, ör, x ve x'. Şu ana kadar indirgemenin zeminini hazırlamaya çalıştık, bundan sonra problemleri çevirmeye çalışacağız. Aşağıda, karşılanabilir bir örnek funksiyonu verilmiştir. Belirlenen kurallar çerçevesinde formülden çizgeye dönüşüme başlarsak, alttaki G çizgeyi elde etmiş olacağız. Dosya:Grafsat.jpg İndirgemeyi açıkça bir şekilde gördükten sonra, yöntemin tutarlığını ispatlamak için iki tane varsayım üzerinde yorum yapılacak: ’nin karşılanabilir (satisfying) olduğunu varsayalım; Son değerin doğru olduğuna göre, her cümlecikte en azında bir tane harfin değeri doğru (1) olması gerekiyor ki, “ve” işleminin sonucu olarak 1 elde edilsin. G dizgesinde her üçlü için doğru değerli harfi temsil eden bir düğüm seçiliyor. Eğer bir cümlecikte birden fazla doğru değerli harf varsa, keyfi olarak doğru olanlar aradında bir tane seçiliyor. Seçilen düğümler k-klik şeklini oluşturuyorlar. Dikkatli bakarsak, her (sayısı k olan) cümlecikten birer harf aldığımızdan dolayı seçili düğüm sayısı k’dır. K-klik içindeki düğümler aynı 3-lü gruptan olamazlar çünkü her 3-lü den sadece bir tane düğüm seçmiş olduk. Aynı zamanda, düğümler tümleyenleri ile birleşemiyorlar çünkü varsayıma göre, birleşmiş harflerin değerinin doğruydu. Bundan dolayı G çizgesi k-klik içeriyor. G dizgesinin k-klik olduğunu varsayalım; Klik içinde olan iki düğüm kesinlikle aynı 3-lüde olamazlar çünkü aynı 3-lüde olan düğümler birbirine bağlı değil. Bundan dolayı k-klikte yer alan düğümlerin her biri farklı 3-lüde yer alır. ’nin değerin doğru atamamızdan dolayı, cümlecikteki harflerin değerlerini doğru varsaymaktır. Bundan dolayı, birbirinin tümleyeni olan düğümler bağlı değil ve aynı klikte yer alamazlar. Değişkenlerin bu gibi değerlerle atanması 'nin değerini doğru yapmış olur ve karşılanabilir olmuş oluyor. Sonuç İlk baştaki amacımız NP sınıfında olan iki problem arasında birbirine indirgeme yapmaktı. 3SAT bir formül, diğer tarafta da Klik bir çizge olduğu halde, ispat sonucunda indirgeme sağlandı ve problemler birbirinin cinsinde gösterilebildi. Kaynakça Michael Sipser, Introduction to the theory of computation 2nd edition, pg.274 Kategori:Karmaşıklık teorisi