Конечный алфавит и функция не вычислимая за полиномиальное t

[grisha111]

Помогите пожалуйста с следующей задачей и скажите где можно про это почитать,
Приведите пример конечного алфавита $\Sigma$ и всюду определенной вычислимой функции из $\Sigma^*$ в $\Sigma^*$, не вычислимой за полиноминальное время.

[mihaild]

А откуда вы взяли эту задачу? (они редко появляются из воздуха, чаще из курсов - а к курсам должна прилагаться литература; и странно давать довольно нетривиальную теорему в виде задачи)
Доказательство есть, например, в "Введении в сложность вычислений" Крупского.