Polynomialzeit berechenbare Funktion

Einfache Sprache

Def. Polynomial berechenbare Funktion

Eine Funktion $f:\Sigma^*\to\Sigma^*$ ist eine Polynomialzeit berechenbare Funktion wenn eine Polynomialzeit Turingmaschine $M$ existiert so, dass für jede Eingabe $w$ terminiert $M$ mit nur $f(w)$ auf dem Ausgabeband.