This flashcard is just one of a free flashcard set. See all flashcards!

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