Definition. polytime computable [polytime-computable]

For some function $f:\Sigma \ast \rightarrow\Sigma \ast$, it is polytime computable if there exists a Turing-machine that when given $x$ as input terminates with $f(x)$ on the tape and runs in time $\text{poly}\left( {|x|} \right)$.