polynomial time computable function

Einfache Sprache

Def. plynomial time computable function

A Funktion $f:\mathbb N \to \mathbb N$ is a polynomial time computable function or time constructible if $f(n)\geq n$ for every $n\in\mathbb N$ and there exists a Turingmaschine $\mathrm{TM}$ that computes $x\mapsto \llcorner f(|x|)\lrcorner$ in time $\mathcal O(f)$.

Beachte das hier $\llcorner\cdot\lrcorner$ die Darstellung der Zahl im Binärsystem.