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

Рассматривается новый подход к изучению категоричности структур, вычислимых за полиномиальное время, который основан на изучении полиномиально вычислимых устойчивых отношений. Показывается, что для вычислимых булевых алгебр с вычислимым множеством атомов и для вычислимых линейных порядков с вычислимым множеством соседних пар эта категоричность равносильна обычной вычислимой категоричности. Строятся примеры, показывающие, что это верно не всегда. Устанавливается связь между размерностями, основанными на вычислимых и полиномиально вычислимых устойчивых отношениях.