Определение.

Функция f(n) называется экспоненциальной, если существуют такие постоянные c₁ > 0, k₁ > 1, c₂ > 0 и k₂ > 1, что с₁k₁ⁿ  f(n)  c₂k₂ⁿ для всех , кроме конечного числа, значений n.

Все функции, полиномиально эквивалентные экспоненте, - экспоненциальны.

Полиномиальность задачи можно проверить на любой вычислительной модели.

0.12. Машина Тьюринга (k-ленточная).

Многоленточная машина Тьюринга (МТ), изображенная на рис.2, состоит из k лент, бесконечно простирающихся вправо. Каждая лента разбита на клетки, каждая клетка содержит один из конечного числа символов на ленте. Одна клетка на каждой ленте обозревается головкой этой ленты. Головка может считывать с ленты и записывать на нее. Работа машины определяется простой программой, называемой управляющим устройством. Оно всегда находится в одном из конечного числа состояний, которое можно рассматривать как номер текущей команды в программе.

Один шаг вычисления на машине Тьюринга состоит в следующем: в соответствии с текущим состоянием управляющего устройства и символами на лентах, обозреваемыми, (т.е. находящимися) под каждой из головок, машина Тьюринга может выполнить некоторые или все из следующих операций:

1) изменить состояние управляющего устройства,

2) напечатать новые символы на лентах вместо старых в каких-нибудь или во всех клетках под головками,

3) сдвинуть какие-нибудь или все головки независимо друг от друга на одну клетку влево (L) или вправо (R) либо оставить на месте (S).

Формально k-ленточная МТ задается семеркой (Q, T, I, , b, q₀, q_f),

где

1) Q - множество состояний.

2) T - множество символов на лентах,

3) I - множество входных символов,

4) b - пустой символ,

5) q₀ - начальное состояние.

6) q_f - заключительное (или допускающее) состояние,

7)  - функция переходов, она отображает некоторое подмножество множества Q*T^k в Q*(T*{L,R,S})^k, т.е. по произвольному набору из состояния и k символов на лентах она выдает новое состояние и k пар, каждая из которых состоит из нового символа на ленте и направления сдвига головки.

Пусть  (q₁, a₁, a₂, ...a_k)=(q (a₁,d₁),(a₂,d₂), ...,(a_k,d_k)) и МТ находится в состоянии q, а ее головка на i-ой ленте обозревает символ a_i, 1 i k. Тогда за один шаг эта машина Тьюринга переходит в состояние q, заменяет a_i на a_i и сдвигает головку на i-ой ленте в направлении (или в

соответствии с) d_i, 1 i k.

Определение.

Временная сложность T(n) машины Тьюринга M равна наибольшему числу шагов, сделанных ею при обработке входа длины n (для всех входов длины n). Если на каком-нибудь входе длины n МТ не останавливается, то для этого n значение T(n) не определено.

Определение.

Емкостная сложность S(n) МТ равна наибольшему расстоянию от левого конца ленты, которое должна пройти головка при обработке входа длины n. Если головка на какой-то ленте неопределенно долго движется вправо, то функция S(n) не определена. Порядок величин при применении в качестве модели МТ обозначается O_mt.