swf: Что-то вы мудрите. Есть сложность по времени, есть сложность по памяти.
Сложность по времени - функция от длины входа.
Вход должен быть закодирован любой разумной схемой кодирования.
Чем разумная схема отличается от неразумной.

Предположим, надо закодировать натуральное число B.
Теперь переходим на язык детерминированных машин Тьюринга.
Если на ленте ДМТ поставить B единичек: 111...111, то число B будет закодировано в унарном коде, это неразумная схема.
Если число B закодировать в двоичном, троичном и т.д. коде, то на ленте будет log(B) единичек (основание логарифма не пишем, т.к. все логарифмы эквивалентны с точностью до константы).
Вот эти log(B) единичек для кодирования число B - разумная схема.
Полиномиальный алгоритм должен иметь выч. сложность p(log(B)), где p - полином.
Всё :)

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833354