Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Eine Reduktion ist eine Technik zum Nachweis, ob eine Sprache rekursiv bzw. rekursiv aufz. oder nicht rekursiv bzw. nicht rek. aufzb. ist.

Diese bildet die Eingabe eines Problems auf die Eingabe eines anderen Problems ab. Sie wird deshalb auch Eingabe-Eingabe-Reduktion bzw. Many-One-Reduktion genannt