İ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.