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:
![](/pool/data/tex/3b31c108ed4b92f74123af169a0e643d.gif)
=>
ist also unter dem Gesichtspunkt der Berechenbarkeit nicht schwerer als ![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/01d66126947a770d765b444db9095131.gif)
![](/pool/data/tex/936d761554105f0e2c87754a9646232a.gif)
![](/pool/data/tex/0c45e03bcc795af48f72c87b6a40ee3b.gif)
![](/pool/data/tex/3b31c108ed4b92f74123af169a0e643d.gif)
=>
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)