Временна́я сложность многомерных машин Тьюринга

Доказано, что работу недетерминированной $m$-мерной машины Тьюринга с временно́й сложностью $t$ можно смоделировать на недетерминированной $k$-мерной ($k\leq m$) машине Тьюринга с временно́й сложностью $t^{1-1/m+1/k+\varepsilon}$ (для любого $\varepsilon>0$). Кроме того, доказано следующее обобщение на многомерный случай известной теоремы Хопкрофта, Пауля и Вэльянта: работу $m$-мерной машины Тьюринга с временно́й сложностью $t\log^{1/m}t$ ($t(n)\geq n$) можно промоделировать на адресной машине, работающей с временно́й сложностью $t$. Библ. – 10 назв.