1) Это список, а не множество из-за возможных повторений.

) Как мы увидим, способ кодирования данных задачи очень важен. Нетрудно показать, что если для распознавания используется ДМТ, то время решения задачи из примера 10.1 составляет в действительности Oj.j.(n2),

где п - длина входа. Но если вход закодировать двоичными числами, то длина входа будет равна сумме логарифмов чисел il, i; и та же стратегия даст алгоритм сложности Ojj(c"), где и - это уже длина двоичного входа и с>1.

. . ., ttj) содержит (где-то внутри себя) символ заключительного состояния q. Языком L{M), допускаемым машиной М, называют множество всех цепочек, допускаемых М.

Пример 10.1. Построим НТМ, допускающую такие цепочки вида

10>10>.. .10*,

что ЧЩч ДЛЯ некоторого множества /е{1,2,. . ., /г}. Иными

словами, цепочка w должна допускаться, если список ) целых чисел iu ii,. . ifc, представленный ею, можно разбить на два подсписка так, чтобы суммы чисел в них были равны. Эта задача известна как задача о разбиении. Доказано, что она NP-полна, если целые числа ij представлены своими двоичными кодами и размером задачи считается длина списка этих двоичных целых чисел

Мы построим трехленточную НМТ М, распознающую этот язык. Она просматривает свою входную ленту слева направо, и каждый раз, когда она доходит до блока вида OV, на вторую или третью ленту добавляются эти ij нулей, причем выбор ленты недетермини-рован. После того как машина дойдет до конца входа, она проверит, совпадают ли числа нулей на лентах 2 и 3, и, если да, допустит вход. Поэтому, если какая-нибудь последовательность выборов, указывающая, в какое из множеств помещать очередное число ij - в первое (на ленту 2) или во второе (на ленту 3), приводит к равным суммам, то эта НТМ допустит вход. Последовательности шагов, приводящие к неравным цепочкам на лентах 2 и 3, не принимаются во внимание, если хотя бы одна последовательность выборов срабатывает. Формально пусть

M = ({q„ qi.....q,}, {О, 1, b, $}, {О, 1}, б, b, q„ q,),

где функция переходов б задана на рис. 10.1.

На рис. 10.2 показаны две из многих последовательностей шагов, которые может сделать на входе 1010010 эта НМТ. Первая приводит к допускающему состоянию, вторая нет. Поскольку по крайней мере одна последовательность шагов приводит к допускающему состоянию, эта НМТ принимает 1010010. □

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

Состояние

Текущий символ на ленте

1 2 3

Новый символ, сдвиг головки на ленте

Новое состояние

Примечания

1, S

$, R

<7i

Машина помечает левые концы лент 2 и 3 знаком S и переходит в состояние q.

1,R 1,R

b, S b, S

b, s b, s

Здесь машина выбирает, писать очередной блок на ленте 2 (q) или 3 (9з).

0, R

1, S Ь, S

О, R Ь, S Ь, L

b.S b,S b,L

0, R

1. s b, S

b,S b,S b, L

0,R b,S b, L

«74

Машина переписывает блок из нулей на ленту 2, затем по достижении единицы на ленте 1 возвращается в состояние q. Если же на ленте 1 достигнут символ Ь,она переходит в состояние q, чтобы сравнить длины лент 2 и 3.

То же, что в состоянии q, но запись на ленту 3.

b,S b,S

0,L $,S

Сравнение длин лент 2 и 3.

Машина допускает вход.

Рис. 10.1. Переходы (шаги) НМТ. Каждая строка представляет один вариант

выбора.

((7„1010010, д,) 1010010, $q„ $q,) Н(1?2010010, $q„ $q,) h-(10(?al0010, Щ„ $q,) (-(10(7il0010, $0q, iq,) Ь(101<7з0010, $0q„ $q,) Ь{1010(7з010, $0q„ $Oqs) b( 10100(7310, $0(7з, $00<7з) h-(10100<7,10, $0q„$00q,) Ь (101001(7,0, $0(7a, $00<7,)

H (10100102, $002, $002)

b(1010010(7„ $0(7,0, $0(7,0) h-(1010010(74, $(/,00, $qfiO) h-(1010010(7,, (7,$00, 9.$00) h-(1010010(7,, (7,$00, ЯЛЩ Вход допускается

((7„ 1010010, (7„, (7„) b(?il010010, $q„ $q,) Н(1<7з010010, $(7з, $(7з) Н(10(7з10010, $<7з, $0(7з) -(10<7il0010, $q„ $0(7J Ь(101(7з0010, $(7з, $0<7з) Ь(1010(7з010, $(7з, $00(7з) Ь(10100(7з10, $(7з, $О00(7з) h-(10100(7,10, $(/„ $000(7i) Ь-(101001(7зО, $(7з. $000(7з) Ь(1010010<7з, $7з,$0000(7з) Н (1010010(7,, ?4$. $000(7,0) Остановка -нет следую-ш,его МО

Рис. 10.2. Две возможные последовательности шагов для НМТ.

которая приводит в допускающее состояние, и емкостную сложность S{n), если для всякой допускаемой входной цепочки длины п найдется последовательность шагов, приводящая в допускающее состояние, в которой число просмотренных головкой клеток на каждой ленте не превосходит S{n).

Пример 10.2. НМТ из примера 10.1 имеет временную сложность 2п+2 (худший случай - вход из п единиц) и емкостную сложность п+1. Другие разумные кодирования задачи о разбиении также дают эту сложность. Например, пусть В (i) - двоичное представление целого числа i и

Lj = #В (iJ #S (fj).. .#В (i) I существует такое множество

/S{1,2.....fe. что Si,= 2]t,l,

iel til f

где # - разделительный маркер. Чтобы распознать Lj, можно построить новую НМТ Mi, работа которой аналогична работе НМТ с рис. 10.1. Отличие состоит в том, что вместо копирования нулей на ленту 2 или 3 Mi запоминает на лентах двоичные числа. Каждое новое двоичное число, встречающееся во входной цепочке, прибавляется к числу на той или другой ленте.