Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
51
reduzierbar
Es seien 
und 
Sprachen über 
. Dann heißt auf reduzierbar (
), wenn es eine berechenbare Funktion 
gibt, sodass für alle 
gilt:
=> ist also unter dem Gesichtspunkt der Berechenbarkeit nicht schwerer als
und Sprachen über . Dann heißt auf reduzierbar (), wenn es eine berechenbare Funktion gibt, sodass für alle gilt:=>
ist also unter dem Gesichtspunkt der Berechenbarkeit nicht schwerer als 