:::: MENU ::::
Hesaplama Teorisi

NP, NP-Complete, NP-Hard nedir?

NP, NP-Complete, NP-Hard nedir?

Bir problem Evet veya Hayır şeklinde sonuç üretiyorsa buna karar problemi denir.

P (Polynomial Time): Polinomsal zamanda çözülebilen karar problemlerinin karmaşıklık sınıfıdır. Yani polinomsal zamanda Evet veya Hayır şeklinde bir çözüm üretilir.

NP (Non-deterministic-polynomial Time): Polinomsal zamanda doğrulanabilen karar problemlerinin karmaşıklık sınıfıdır. Burada problemin bir çözümü olup olmadığı ile ilgilenilmiyor.

NP-Complete: Her adımdaki çözümleme zamanı kendinden önceki adımdaki çözümleme zamanlarından daha fazla olduğu için bu problem tiplerinin çokterimli zamanda (polynomial time) çözülmesi mümkün değildir. NP-Complete bir problem Belirsiz(Non-Deterministic) Turing Makinesi tarafından belirli zamanda çözülebilmektedir.

NP-Hard: Polinomsal zamanda bir çözümü olduğunu ispatlayamadığımız karar problemlerinin karmaşıklık sınıfıdır.3SAT ve Halting problemi NP-Hard problemlerdir.

P=NP? sorusunun cevabı aranmaktadır. P=NP ispatlanabilirse çözümü olmayan problemlere de çözümler üretilecektir.

Aşağıdaki her iki durum için karmaşıklık sınıfları görselleştirilmiştir:

P-NP-NP-Complete-NP-Hard



Özyineleme (Recursion) teoremi nedir?

Özyineleme (Recursion) teoremi nedir?

T, t:Ʃ^*×Ʃ^*→Ʃ^* fonksiyonunu hesaplayan bir Turing makinesi olsun. Ve bir r:Ʃ^*→Ʃ^* fonksiyonunu hesaplayan, her bir w için r(w)=t(,w) olan bir R Turing makinesi olsun. Kendi tanımını elde edip ardından bununla hesaplama yapabilen bir Turing makinesi yapmak için yalnızca, makinenin tanımını ekstra bir giriş olarak alan, yukarıda belirtildiği gibi bir T makinesi yapmak gerekir. Ardından recursion teoremi, tıpkı T gibi çalışan ancak tanımı otomatik olarak yapılmış yeni bir R makinesi üretir.

Başka bir açıdan:

Özyineleme (Recursion) teoremi, hesaplanabilirlik teorisinde ileri düzey çalışmalarda önemli bir rol oynayan matematiksel bir yaklaşımdır. Matematiksel mantığa, kendi kendini yeniden üreten sistemlerin teorisine ve hatta bilgisayar virüslerine bağlantıları vardır.

Özyineleme (Recursion) teoremini izah etmek için yaşam araştırmasında kullanılan bir paradokstan bahsedelim. Kendi kopyalarını oluşturabilen makineler yapma ihtimali var mıdır? sorusuna cevap aranmaktadır.

1. Canlılar makinelerdir.
2. Canlılar kendiliğinden çoğalabilirler.
3. Makineler kendi kendine çoğalamazlar.

Özyineleme (Recursion) teoremi 3.durumun yanlış olduğunu ortaya koyar.

Özyineleme (Recursion) teoremi:

T, t:E*xE*->E* fonksiyonunu işleyen bir Turing makinesidir. R, r:E*->E* fonksiyonunu her w girdisi için işleyen bir Turing makinesidir. r(w)=t(,w).

Bu tanıma göre T Turing Makinesi, R Turing makinesini otomatik olarak üretir.

Bilgisayar virüsleri, kendi kendilerine çoğalan bir yapıdadırlar.

Videolu anlatım:


İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme bir problemi başka bir probleme dönüştürme işlemidir, böylece ikinci problemin çözümü birinci problemi çözmek için kullanılabilir.

İndirgenebilirlik, A ve B gibi iki problemi içerir. Eğer A, B’ye indirgenebilirse, B’yi çözmek için A’yı kullanabilirsiniz.

Örneğin bir şehirde yolunuzu bulmak istiyorsunuz. Bir haritanız olmuş olsa yolları daha rahat bulabileceğinizi biliyorsunuz. Böylece şehirde yol bulma problemini bir harita elde etme problemine indirgemiş oldunuz. Haritanız olduğu zaman şehirde yolunuzu bulabilirsiniz.

Burada A-> Şehirde Yol Bulma B-> Harita Edinme

İndirgenebilirlik, A veya B’nin çözümü için bir yorumda bulunmaz sadece B problemini çözdüğünüz zaman A problemini de çözebileceğinizi belirtir.

Bir başka örnek:
A->Konya’dan İstanbul’a gitmek
B->Konya-İstanbul uçak bileti almak
C->Bilet almak için para kazanmak
D->Para kazanmak için iş bulmak

Matematiksel örnekler verecek olursak:
-Dikdörtgen alanını bulmak, genişliğini ve yüksekliğini ölçmek için indirgemedir.
-Bir dizi doğrusal denklem çözmek, bir matrisi tersine çevirmek için indirgemedir.

İndirgenebilirlik, problemleri karar verilebilir (decidable) ve karar verilemez (undecidable) olarak sınıflandırmada ve karmaşıklık teorisinde (complexity theory) önemli rol oynar.

A, B’ye indirgenebilir olduğunda, A’yı çözmek B’yi çözmekten daha zor olamaz çünkü B’nin çözümü A’ya bir çözüm getirir.

Hesaplanabilirlik teorisi açısından, eğer A, B’ye indirgenebilir ve B karar verilebilir ise, A da karar verilebilirdir. Benzer şekilde, A, karar verilemez ve B’ye indirgenebilirse, B karar verilemezdir.


Sayfalar:12345678