Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Bu maddede birçok sorun bulunmaktadır. Lütfen sayfayı geliştirin veya bu sorunlar konusunda bir yorum yapın.
|
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ş
İndirgeme4 Mayıs 2009 tarihinde Wayback Machine sitesinde arşivlendi.: A problemi B problemine indirgenebiliyorsa, B problemin çözümü A’nın çözümü için kullanılabilir. Karmaşıklık11 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi., 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 =? NP21 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi. 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 14 Mayıs 2011 tarihinde Wayback Machine sitesinde arşivlendi. 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. 
3SAT ve Klik problemlerin Karmaşıklık Sınıflarındaki yeri
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. 3SAT21 Mayıs 2009 tarihinde Wayback Machine sitesinde arşivlendi. problemi, SAT karşılanabilir (satisfiable) proleminin cümlecikleri 3 harften oluşmuş özel bir halidir.
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, x1 ve x1'.
Ş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.
İ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:
![image]()
’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
[1]16 Ocak 2010 tarihinde Wayback Machine sitesinde . Michael Sipser, Introduction to the theory of computation 2nd edition, pg.274
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bu maddede bircok sorun bulunmaktadir Lutfen sayfayi gelistirin veya bu sorunlar konusunda tartisma sayfasinda bir yorum yapin Bu madde Vikipedi bicem el kitabina uygun degildir Maddeyi Vikipedi standartlarina uygun bicimde duzenleyerek Vikipedi ye katkida bulunabilirsiniz Gerekli duzenleme yapilmadan bu sablon kaldirilmamalidir Ocak 2010 Bu maddenin veya bolumun ozgun arastirma dogrulanamaz veya yoruma dayali ifadeler icerdigi dusunulmektedir Lutfen iddialari kontrol ederek ve yeni kaynaklar ekleyerek gelistirin Ozgun arastirmadan olusmus ifadeler kaldirilabilir Ayrintilar maddenin tartisma sayfasinda bulunabilir Bu maddenin veya maddenin bir bolumunun gelisebilmesi icin alakali konuda uzman kisilere gereksinim duyulmaktadir Ayrintilar icin lutfen tartisma sayfasini inceleyin veya yeni bir tartisma baslatin Konu hakkinda uzman birini bulmaya yardimci olarak ya da maddeye gerekli bilgileri ekleyerek Vikipedi ye katkida bulunabilirsiniz Kasim 2012 3SAT ve KLIK problemleri Turing makinasindan polinom zamanda kararlastirilabilen NP problemleri arasinda yer alir Bu problemlerin birbirinin cinsine cevrilmesine indirgeme denilir GirisIndirgeme4 Mayis 2009 tarihinde Wayback Machine sitesinde arsivlendi A problemi B problemine indirgenebiliyorsa B problemin cozumu A nin cozumu icin kullanilabilir Karmasiklik11 Subat 2010 tarihinde Wayback Machine sitesinde arsivlendi parcalari ve onlarin duzeni kavramasi zor olan bir sistemdir Karmasiklik Kurami sirasinda ise cozumleri zor olan problemerlerin birbirine indirgeyerk cozumlerini kolaylastirilmaya calisiliyor Bununla ilgili olan P NP21 Subat 2010 tarihinde Wayback Machine sitesinde arsivlendi sorusunun cevabi da ayni sekilde ilk basta problemleri indirgeyerek basitlestirmeye calisilir sonra da cozumleri olan problemleri kullanarak daha karmasik olanlarin cozumlerine bakilir Bu sekilde P ve NP siniflarindaki problemleri arasinda bir iliski bulunursa cozume dogru gidebiliriz NP sininfinda problemlerini cozmek icin de ayni sekilde indirgemeye basvurulur ama bu defa Polinom zamanda indirgeme 14 Mayis 2011 tarihinde Wayback Machine sitesinde arsivlendi olur Polinom Zamanda IndirgemeA dili B diline polinom zamanda indirgenebilir A pB displaystyle A leq pB ancak ve ancak f S S displaystyle f Sigma to Sigma diye polinom zamanda calisan bir hesaplama funksiyonu varsa ve her w displaystyle w icin w A f w B displaystyle w in A Leftrightarrow f w in B gecerlidir 3SAT ve Klik problemlerin Karmasiklik Siniflarindaki yeriNP sifinda yer alan problemler arasinda 3SAT ve Klik problemleri de bulunur Okla gosterildigi gibi 3SAT ve Klik arasinda indirgeme islemi yapilacak 3SAT21 Mayis 2009 tarihinde Wayback Machine sitesinde arsivlendi problemi SAT karsilanabilir satisfiable proleminin cumlecikleri 3 harften olusmus ozel bir halidir 3SAT ϕ ϕkarsilanabilir bir 3CNF formuludur or 1 ϕ a1 b1 c1 a2 b2 c2 ak bk ck KLIK G k G k klik iceren bir yonsuz cizgedir displaystyle begin aligned 3SAT amp left left langle phi right rangle mid phi text karsilanabilir bir 3CNF formuludur right text or 1 phi amp a 1 lor b 1 lor c 1 land a 2 lor b 2 lor c 2 land ldots land a k lor b k lor c k text KLIK amp left left langle G k right rangle G text k klik iceren bir yonsuz cizgedir right end aligned Resimde goruldugu gibi 1 2 5 dugumler arasinda klik oluyor Ispat fikriProblemlerin tanimlarindan da yola cikarak 3SAT problemin bir formul KLIK probleminin de bir cizge oldugunu fark ettik Problemleri indirgemek ve cozumlemek icin ilk basta birbirinin formatina gosterilmeleri ve cevirilmeleri gerekiyor Ornek 1 den goruldugu gibi 3SAT cumlcikleri ve displaystyle wedge baglaciyla baglanmis ve her cumlesi veya displaystyle vee baglaciyla baglanmis 3 harften olusuyor Klik problemi ise resimde gosterildigi gibi bir cizgenin icinde birbirine baglanan dugumlerle ilgilidir Bu iki problemi birbirine donusturmenin indirgemenin yolu formulu cizge gibi cizgeyi de formul haline donusturmekten gecer Belirli cizgelerin icinde k buyuklukteki klikleri belirli karsilanabilir formullerle uyusuyor Surulen bu fikirler uzerinden yola cikarak NP sininfinda olan iki problemin arasinda birbirinin cinsine taklitini kullanarak polinom zamanda indirgemeyi basarmaya calisacagiz Ispatϕ displaystyle phi k cumlecikten olusan bir formul olsun f displaystyle f indirgemesinin sonucu olarak G displaystyle G yonsuz cizge olmak uzere G k displaystyle langle G k rangle katari uretilmesi bekleniyor Bunun yapisi soyle Cizgedeki dugumler aralarinda 3 lu olacak sekilde gruplaniyor ve sirayla t1 t2 t3 tk displaystyle t 1 t 2 t 3 ldots t k Her bir 3 lu formuldeki bir cumlecige her bir dugum de cumlecikteki bir harfe denk geliyor Dolayisiyla G cizgesideki her dugum ϕ displaystyle phi nin bir literaline karsilik gelir Bu cevirmeyi yaparken formulde ve veya baglaclari goz onune alarak cizgedeki dugumler arasinda alttaki kurallar uygulanmasi gerekiyor Ayni 3 lu grup icinde yer alan dugumler arasinda baglanti yok Birbirinin tumleyeni olan iki dugum arasinda baglanti yok or x1 ve x1 Su ana kadar indirgemenin zeminini hazirlamaya calistik bundan sonra problemleri cevirmeye calisacagiz Asagida karsilanabilir bir ornek funksiyonu verilmistir ϕ x1 x1 x2 x1 x2 x2 x1 x2 x2 displaystyle phi x 1 vee x 1 vee x 2 wedge overline x 1 vee overline x 2 vee overline x 2 wedge overline x 1 vee x 2 vee x 2 Belirlenen kurallar cercevesinde formulden cizgeye donusume baslarsak alttaki G cizgeyi elde etmis olacagiz Indirgemeyi acikca bir sekilde gordukten sonra yontemin tutarligini ispatlamak icin iki tane varsayim uzerinde yorum yapilacak ϕ displaystyle phi nin karsilanabilir satisfying oldugunu varsayalim Son degerin dogru olduguna gore her cumlecikte en azinda bir tane harfin degeri dogru 1 olmasi gerekiyor ki ve isleminin sonucu olarak 1 elde edilsin G dizgesinde her uclu icin dogru degerli harfi temsil eden bir dugum seciliyor Eger bir cumlecikte birden fazla dogru degerli harf varsa keyfi olarak dogru olanlar aradinda bir tane seciliyor Secilen dugumler k klik seklini olusturuyorlar Dikkatli bakarsak her sayisi k olan cumlecikten birer harf aldigimizdan dolayi secili dugum sayisi k dir K klik icindeki dugumler ayni 3 lu gruptan olamazlar cunku her 3 lu den sadece bir tane dugum secmis olduk Ayni zamanda dugumler tumleyenleri ile birlesemiyorlar cunku varsayima gore birlesmis harflerin degerinin dogruydu Bundan dolayi G cizgesi k klik iceriyor G dizgesinin k klik oldugunu varsayalim Klik icinde olan iki dugum kesinlikle ayni 3 lude olamazlar cunku ayni 3 lude olan dugumler birbirine bagli degil Bundan dolayi k klikte yer alan dugumlerin her biri farkli 3 lude yer alir ϕ displaystyle phi nin degerin dogru atamamizdan dolayi cumlecikteki harflerin degerlerini dogru varsaymaktir Bundan dolayi birbirinin tumleyeni olan dugumler bagli degil ve ayni klikte yer alamazlar Degiskenlerin bu gibi degerlerle atanmasi ϕ displaystyle phi nin degerini dogru yapmis olur ve karsilanabilir olmus oluyor SonucIlk bastaki amacimiz NP sinifinda olan iki problem arasinda birbirine indirgeme yapmakti 3SAT bir formul diger tarafta da Klik bir cizge oldugu halde ispat sonucunda indirgeme saglandi ve problemler birbirinin cinsinde gosterilebildi Kaynakca 1 16 Ocak 2010 tarihinde Wayback Machine sitesinde Michael Sipser Introduction to the theory of computation 2nd edition pg 274