OMANSAK

İndirgeme      İndirgeme tanımı olarak bir problemi başka bir probleme dönüştürmek için hesaplanabilir fonksiyonların kullanılmasıdır. Özellik 1.a :     Herhangi bir A problemi, B problemine indirgenirse, o zaman herhangi      bir B çözümü A'nın bir çözümünü bulmak için kullanılabilir.     " Burada A yada B problemlerinin kendilerinin çözümü hakkında      bir varsayım yoktur" Örnek Problem 1.1 :  "Malatya'dan İstanbul'a gitmek" Çözüm 1.1:      Burada ki problemi şu şekilde indirgemeler yapabiliriz Gitmek için uçak bileti almaya indirgeme Uçak bileti almak için paraya kazanmaya indirgeme Para kazanmak için işe girmeye indirgeme Örnek Problem 1.1 için belirtilen çözüm de görüldüğü gibi bir problemini başka bir probleme indirgeyerek ana problemin çözümünde kullanabiliriz. Eğer A problemi, B problemine indirgenebiliyorsa: A problemi B probleminden daha zor olamaz. A kararlı ise B de kararlıdır ( decidable )     A kararsız ise B de kararsızdır ( undecidable )