Структуры, вычислимые за полиномиальное время. I

Доказывается, что любая вычислимая локально конечная структура с конечным числом функций обладает представлением, вычислимым за полиномиальное время. Кроме того, структура, вычислимая за полиномиальное время, является полиномиально категоричной тогда и только тогда, когда она конечна. Если структура вычислима за полиномиальное время и локально конечна, то она слабо полиномиально категорична (т.е. категорична относительно примитивно рекурсивных изоморфизмов) тогда и только тогда, когда конечна.