Неформально алгоритм — это однозначно определенная совокупность инструкций по преобразованию исходных данных в результат, причем все инструкции элементарны, т.е. при их выполнении "нам придется только механически следовать предписаниям, как если бы мы были роботами: от нас не потребуется ни понимания, ни искусства, ни изобретательности" [5, с. 270]. Формализовать это понятие можно различными способами.
Обычно подразумевается, что каждый алгоритм решает какую-то вычислительную задачу. С формальной точки зрения, вычислительная задача - это функция
F: входные данные -> результат,
Что такое "входные данные" и "результат"? Рассмотрим, например, задачу об умножении двух многочленов с целыми коэффициентами. Тогда входные данные - это пара многочленов. Проблема в том, как записать эти многочлены, чтобы их можно было ввести в компьютер. Машины Тьюринга, которые мы рассматриваем ниже, понимают лишь конечные последовательности символов (слова) из некоторого конечного множества A, называемого внешним алфавитом. Поэтому строгая формулировка вычислительной задачи должна включать в себя алфавит и способ кодировки входных данных. Например, можно записать пару многочленов с использованием 10 цифр, символа переменной x, знаков +, -, * и скобок: (x**2-5)(-4*x+1). В другой кодировке коэффициенты записываются в двоичной системе счисления и перечисляются через запятую; два многочлена разделяются звездочкой: 1, 0, -101* -100, 1. Таким образом, мы имеем две различные вычислительные задачи. С практической точки зрения, обе задачи эквивалентны, поскольку перевод из одной кодировки в другую осуществляется с помощью полиномиального алгоритма. Пока определения полиномального алгоритма у нас нет, давайте будем формалистами: вычислительная задача - это частичнаяПод частичной функцией на множестве X здесь и далее понимается функция, область определения которой содержится в X. функция F: A* -> A* (где A* обозначает множество конечных слов в алфавите $$A$$ ). Потом мы позволим себе некоторую вольность и будем говорить о задаче умножения многочленов или разложения целого числа на множители, имея ввиду, что все разумные кодировки эквивалентны (т.е. переводятся друг в друга при помощи полиномиальных алгоритмов). Однако нужно помнить, что не всякая кодировка является "разумной". Нехорошо, например, представлять натуральное число n набором из n звездочек, потому что длина такой записи экспоненциально велика по сравнению с двоичной или десятичной записью. Заметим также, что в некоторых задачах нет хорошего выбора "разумной" кодировки, в таких случаях (они нам не встретятся) необходимо указывать кодировку всякий раз, когда формулируется задача.
Теперь дадим формальное определение алгоритма.
Машины Тьюринга.
Машина Тьюринга (сокращенно МТ) однозначно задается указанием набора $$(\cal S, \_, \cal A, \cal Q, q_{0}, \delta)$$, где $$\cal S$$, $$\cal A$$, $$\cal Q$$ — конечные множества, причем $$\cal A\subset\cal S$$ ; $$\_$$ — некоторый элемент $$\cal S\setminus \cal A$$ ; $$q_{0}$$ — некоторый элемент $$\cal Q$$, а $$\delta$$ — некоторая (частичная, вообще говоря) функция из $$\cal Q\times\cal S$$ в $$\cal Q\times\cal S\times\{-1,0,1\}$$.
Составляющие части МТ называются так:
$$\cal S$$ — алфавит,
$$\_$$ — пустой символ (или пробел),
$$\cal A$$ — внешний алфавит,
$$\cal Q$$ — множество состояний управляющего устройства,
$$q_{0}$$ — начальное состояние,
$$\delta$$ — функция переходов.
Состояние МТ задается тройкой $$(\sigma,p,q)$$, где $$\sigma$$ — бесконечное слово в алфавите $$\cal S$$, т.е. произвольная последовательность $$s_0,\dots, s_n,\dots$$ элементов $$\cal S$$ ; $$p$$ — неотрицательное целое число; $$q\in\cal Q$$. Символы слова $$\sigma$$ будем, как это принято, представлять записанными на ленте, разбитой на ячейки, по ячейке на символ. На ленте также имеется головка, которая расположена над ячейкой с номером $$p$$. Наглядно это изображается так:
Помимо ленты машина Тьюринга имеет управляющее устройство, состояние которого задается элементом $$q$$ множества $$\cal Q$$.
Состояния МТ меняются дискретно. За один такт работы управляющее устройство выполняет следующие действия (полагаем, что МТ находится в состоянии $$(\sigma,p,q)$$ ):
читает символ, находящийся под головкой (т.е. определяет $$s_p$$ );
вычисляет значение функции переходов: $$\delta(q,s_p)=(q',s,\Delta p)$$ (если функция переходов на паре $$(q,s_p)$$ не определена, то останавливает машину Тьюринга);
записывает на ленту в ячейку $$p$$ символ $$s$$, сдвигает головку на $$\Delta p$$ и переходит в состояние $$q'$$ (другими словами, новое состояние машины задается тройкой $$((s_0,\dots,s_{p-1},s,s_{p+1},\dots), p+\Delta p,q')$$ );
если $$p+\Delta p<0$$, то останавливает машину.
Пожалуй, всякий согласится, что эти действия не требуют ни понимания, ни искусства, ни изобретательности.
Работа машины Тьюринга будет всегда начинаться из состояния $$(\alpha\_\dots,0,q_0)$$, где за конечным словом $$\alpha$$, состоящим из символов внешнего алфавита (множество таких слов обозначается $$\cal A^*$$ ), следует бесконечное слово, целиком состоящее из пустых символов. Слово $$\alpha$$ будем называть входом МТ. В любой момент времени слово, записанное на ленте, однозначно записывается в виде $$\sigma\_\dots$$, где последний символ слова $$\sigma$$ — не пустой, а за ним идут только пустые символы. Будем называть слово $$\sigma$$ используемой частью ленты.
Выполняя один такт работы за другим, машина Тьюринга порождает последовательность состояний $$(\sigma_0,0,q_0), \,(\sigma_1,p_1,q_1), \, (\sigma_2,p_2,q_2),\,\dots$$
Если МТ останавливается, используемая часть ленты в достигнутом перед остановкой состоянии называется результатом работы МТ.
Вычислимые функции и разрешимые предикаты.
Каждая машина Тьюринга $$М$$ вычисляет частичную функцию $$\ph_М$$ из $$\cal A^*$$ в $$\cal A^*$$, отображающую вход $$\alpha$$ в результат работы МТ на входе $$\alpha$$ при условии, что результат работы является словом во внешнем алфавите. Для входов, на которых машина не останавливается или результат содержит символы из $$\cal S\setminus\cal A$$, функция $$\ph_М$$ не определена. Из определения ясно, что любая МТ вычисляет ровно одну функцию (быть может, нигде не определенную).
Определение 1.1 Частичная функция $$f$$ из $$\cal A^*$$ в $$\cal A^*$$ называется вычислимой, если существует машина Тьюринга $$М$$, для которой $$\ph_М=f$$. При этом будем говорить, что $$f$$ вычислима на $$М$$.
Не все функции вычислимы. Это ясно из сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счетное множество). Более интересные примеры см. в задачах 1.3-1.5.
Под предикатом будем понимать некоторое условие, которое выполняется (предикат истинен) или не выполняется (предикат ложен) для каждого слова из $$\cal A^*$$. Определенные таким образом, предикаты легко отождествляются с языками (подмножествами слов в $$\cal A^*$$ ) — предикату соответствует множество слов, на которых он истинен. Каждому предикату сопоставим характеристическую функцию, которая равна 1 на множестве слов, для которых предикат истинен, и равна 0 на множестве слов, для которых предикат ложен. Мы будем обозначать характеристическую функцию так же, как и сам предикат. Предикат разрешим, если его характеристическая функция вычислима. О машине Тьюринга, вычисляющей характеристическую функцию предиката, будем говорить, что она дает ответ ("да" или "нет") на вопрос "истинно ли значение предиката на входе $$\alpha$$?"
Понятия вычислимой функции и разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных.
Пусть $$\cal A$$ — некоторый алфавит, а $$n$$ — натуральное число. Пусть $$M$$ — машина Тьюринга с внешним алфавитом $$\cal A\cup\{\#\}$$. Построим частичную функцию $$\ph_{M,n}$$ из $$(\cal A^*)^n$$ в $$\cal A^*$$ так: $$\ph_{M,n}(\alpha_1,\dots,\alpha_n)=y$$, если результат работы машины $$M$$ на входе $$\alpha_1\#\alpha_2\#\dots\#\alpha_n\#$$ совпадает со словом $$y$$. Если машина не останавливается или на ленте записано что-нибудь не то (например, символы не из алфавита $$\cal A$$ и т.п.), то $$\ph_{M,n}(\alpha_1,\dots,\alpha_n)$$ не определена.
Определение 1.2. Частичная функция $$f$$ из $$(\cal A^*)^n$$ в $$\cal A^*$$ называется вычислимой, если существует машина Тьюринга $$М$$, для которой $$\ph_{М,n}=f$$.
Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима.
Нас будут интересовать ресурсы, требующиеся для вычислений. Два важнейших ресурса — время и память. Будем говорить, что машина Тьюринга $$M$$ работает за время $$T_М(n)$$, если максимальное (по всем входам длины $$n$$ ) количество тактов, которое проработает $$М$$ до остановки, равно $$T_М(n)$$. Аналогично, машина Тьюринга $$M$$ работает на памяти $$S_М(n)$$, если наиболее удаленное от начала ленты положение головки при вычислениях на входах длины $$n$$ равно $$S_М(n)$$.
Вычисления на машинах Тьюринга.
Очевидно, что МТ задает алгоритм в смысле приведенного выше неформального определения. Обратное утверждение называется тезисом Черча:
"любой алгоритм может быть реализован машиной Тьюринга"
Не вдаваясь в обсуждение тезиса Черча, заметим, что в настоящее время нет серьезных оснований подвергать его сомнению. Все известные в настоящее время алгоритмы реализуются машинами Тьюринга. Подробное изложение теории алгоритмов читатель может найти в книгах [1, 5, 6, 10, 13, 16, 17]. Мы же ограничимся краткими неформальными пояснениями приемов программирования на машинах Тьюринга.
Возможности машины Тьюринга при таком неформальном обсуждении — это возможности человека с ограниченной памятью, карандашом и ластиком, которому вручили неограниченной (бесконечной) толщины тетрадь. Страницы тетради имеют ограниченный размер (все возможные варианты заполнения страницы образуют алфавит МТ при строгом описании). На первых страницах тетради записано входное слово — по одному символу (из внешнего алфавита) на страницу. Человек может листать тетрадь, стирать символы, записывать новые. Заканчивается эта его деятельность тем, что он закрывает тетрадь (сдвиг головки влево в положении 0) и возвращает результат своей работы.
Представив себя в такой ситуации, легко сообразить, что можно, запоминая несколько символов, выполнять любые действия на ограниченном количестве подряд идущих страниц; можно ставить на страницах дополнительные пометки (ограниченное количество на каждой); можно листать тетрадь, пока не найдется нужная пометка; можно копировать символы на свободные страницы тетради. Свободные места на страницах можно также использовать для хранения вспомогательных слов произвольной длины (как и входное слово, они записываются по одному символу на страницу), над которыми может поработать другой человек (это называется "вызов подпрограммы"). В частности, эти вспомогательные слова позволяют поддерживать счетчики (целочисленные переменные). Используя счетчики, можно адресоваться к ячейкам памяти по их номеру.
Поскольку описание любой машины Тьюринга является конечным объектом, его можно закодировать словом в некотором алфавите. В нашей неформальной ситуации легко понять, что существует универсальная машина Тьюринга $$U$$, которая, получая на вход пару $$([М],x)$$, дает выход $$\ph_M(x)$$. Здесь через $$[М]$$ обозначено описание некоторой машины Тьюринга $$М$$. Действительно, предположим, что тетрадь начинается со страниц, где записаны инструкции по работе. Тогда выполнять эти инструкции можно следующим образом: пометим текущую страницу; пролистаем тетрадь до начального раздела, содержащего инструкции; найдем нужную инструкцию; вернемся назад и выполним ее.
Сложностные классы.
Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма.
Формализовать это понятие непросто. Принятый сейчас способ состоит в том, что выделяются классы тех функций или предикатов, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы.Принадлежность функции тому или иному сложностному классу служит удобной характеристикой возможностей ее эффективного вычисления, не связанной с конкретными реализациями алгоритмов.
Наиболее важные классы получаются, если накладывать ограничения на рост времени работы и/или используемой памяти в зависимости от длины входного слова. А наиболее важное различие между эффективными и неэффективными вычислениями задается функциями полиномиального роста. Функция $$f(n)$$ — полиномиального роста, если для некоторой константы $$d$$ при достаточно больших $$n$$ выполняется неравенство $$f(n)\leq n^d$$. В этом случае будем использовать обозначение $$f(n)=\poly(n)$$.
Определение 1.3. Предикат $$f$$ на множестве $$\cb^*$$ принадлежит классу $$\P$$ (и называется полиномиально вычислимым ), если его характеристическая функция вычислима на машине Тьюринга $$М$$, для которой $$T_М(n)=\poly(n)$$.
Определение 1.4. Предикат $$f$$ на множестве $$\cb^*$$ принадлежит классу $$\PSPACE$$, если его характеристическая функция вычислима на машине Тьюринга $$М$$, для которой $$S_М(n)=\poly(n)$$.
По аналогии с предикатами можно определить и функции, вычислимые за полиномиальное время, и функции, вычислимые на полиномиальной памяти. Для классов таких функций также используются обозначения $$P$$ и $$PSPACE$$, так что точный смысл этих обозначений нужно восстанавливать из контекста.
Схемы
Схема (булева) — это способ вычислить функцию $$f\colon\cb^n\double\to\cb^m$$. Помимо исходных переменных $$x_1,\dots, x_n$$, для которых вычисляется значение $$f$$, схема использует некоторое количество вспомогательных переменных $$y_1,\dots, y_s$$ и некоторый набор ( базис ) булевых (т.е. принимающих значения 0 или 1) функций $$\cal F$$. Схема $$S$$ в базисе $$\cal F$$ определяется последовательностью присваиваний $$Y_1,\dots, Y_s$$. Каждое присваивание $$Y_i$$ имеет вид $$y_i:=f_j(u_{k_1},\dots,u_{k_r})$$, где $$f_j(\cdot)\in\cal F$$, а переменная $$u_{k_p}$$ ( $$1\leq p\leq r$$ ) — это либо одна из исходных переменных $$x_t$$ ( $$1\leq t\leq n$$ ), либо вспомогательная переменная $$y_l$$ с меньшим номером ( $$1\leq l<i$$ ). Таким образом, для каждого набора значений исходных переменных последовательное выполнение присваиваний, входящих в схему, однозначно определяет значения всех вспомогательных переменных. Результатом вычисления считаются значения последних $$m$$ переменных $$y_{s-m+1},\dots,y_s$$.
Схема вычисляет функцию $$f$$, если для любых значений $$x_1,\dots,x_n$$ исходных переменных результатом вычисления является $$f(x_1,\dots,x_n)$$.
Схема называется формулой, если каждая вспомогательная переменная используется в правой части присваиваний только один раз. (Обычные математические формулы именно так задают последовательность присваиваний: "внутри" формул не принято использовать ссылки на их части или другие формулы.)
Схему можно также представлять в виде ориентированного ациклического графа, у которого вершины входной степени 0 ( входы ) помечены исходными переменными; остальные вершины ( функциональные элементы ) помечены функциями из базиса (при этом входная степень вершины должна совпадать с количеством аргументов ее пометки); ребра помечены числами, указывающими номера аргументов; вершины выходной степени 0 ( выходы ) помечены переменными, описывающими результат работы схемы. Вычисление на графе определяется индуктивно: как только известны значения всех вершин $$y_1,\dots,y_{k_v}$$, из которых ведут ребра в данную вершину $$v$$, вершина $$v$$ получает значение $$y_v\double=f_v(y_1,\dots,y_{k_v})$$, где $$f_v$$ — базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются на пути к выходным вершинам, так что они никак не влияют на результат вычисления.
Базис называется полным, если для любой булевой функции $$f$$ есть схема в этом базисе, вычисляющая $$f$$. Ясно, что в полном базисе можно вычислить произвольную функцию $$f\colon\cb^n\to\cb^m$$ (такую функцию можно представить как упорядоченный набор из $$m$$ булевых функций).
Булева функция может быть задана таблицей значений. Приведем таблицы значений для трех функций$$\NOT(x)=\neg x,\ \OR(x_1,x_2)= x_1\vee x_2,\ \AND(x_1,x_2)=x_1\wedge x_2$$
( отрицание, дизъюнкция, конъюнкция ), образующих полный базис, который будем считать стандартным. В дальнейшем имеются в виду схемы именно в этом базисе, если явно не указано что-либо иное.$$\begin{array}{c|cccc|cccc|c}
x\NOT\quad x_1x_2\OR\quad x_1x_2\AND\\
\cline{1-2}\cline{4-6}\cline{8-10} 01 \quad 000 \quad 000\\
10 \quad 011 \quad 010\\ \multicolumn{2}{c}{} \quad
101 \quad 100\\ \multicolumn{2}{c}{} \quad 111
\quad 111\\ \end{array}$$
Конъюнкция и дизъюнкция определяются для произвольного числа булевых переменных аналогичным образом: конъюнкция равна 1 только тогда, когда все аргументы равны 1, а дизъюнкция равна 0 только тогда, когда все аргументы равны 0. В стандартном базисе они очевидным образом вычисляются схемами (и даже формулами) размера $$n-1$$.
Теорема 1.1. Базис $$\{\NOT,\OR,\AND\}$$ — полный.
Доказательство. Литералом будем называть переменную или ее отрицание. Конъюнкцией литералов (это схема и даже формула) легко представить функцию $$\chi_u(x)$$, которая принимает значение 1 ровно один раз: при $$x=u$$. Если $$u_i=1$$, включаем в конъюнкцию переменную $$x_i$$, если $$u_i=0$$, то включаем в конъюнкцию $$\neg x_i$$. Произвольная функция $$f$$ может быть представлена в виде
$$f(x)=\bigvee_{u: f(u)=1}\chi_u(x).$$
В таком случае говорят, что $$f$$ представлена в дизъюнктивной нормальной форме (ДНФ), т.е. как дизъюнкция конъюнкций литераловДалее нам еще потребуется и конъюнктивная нормальная форма (КНФ) — конъюнкция дизъюнкций литералов.
Как уже говорилось, дизъюнкция нескольких переменных выражается формулой в стандартном базисе.
Размером схемы называется количество присваиваний в схеме. Минимальный размер схемы в базисе $$\cal F$$, вычисляющей функцию $$f$$, называется схемной сложностью функции $$f$$ в базисе $$\cal F$$ и обозначается $$c_\cal F(f)$$. Переход от одного полного конечного базиса к другому полному конечному базису меняет схемную сложность функций на множитель $$O(1)$$. Так что в асимптотических оценках выбор конкретного полного базиса неважен и поэтому будем использовать обозначение $$c(f)$$ для схемной сложности $$f$$ в конечном полном базисе.
Каждый предикат $$f$$ на множестве $$\cb^*$$ определяет последовательность булевых функций $$f_n\colon \cb^n\to\cb$$ следующим образом: $$f_n(x_1,x_2,\dots,x_n)= f(x_1x_2\dots x_n)$$, где справа стоит характеристическая функция предиката $$f$$.
Определение 1.5. Предикат $$f$$ принадлежит классу $$P/poly$$, если $$c(f_n)=\poly(n)$$.
Теорема 1.2. $$\P\subset P/poly$$.
Если МТ работает за полиномиальное время, то и память, которую она использует, ограничена полиномом. Поэтому весь процесс вычисления на входном слове $$x$$ длины $$n$$ можно представить таблицей вычисления размера $$T\times S$$, где $$T= \poly(n)$$, $$S= \poly(n)$$.
(рис 1.1) Строка с номером $$j$$ таблицы задает состояние МТ после $$j$$ тактов работы. Символы $$\Gamma_{j,k}$$, записанные в таблице, принадлежат алфавиту $$\cal S\times\{\emptyset\cup\cal Q\}$$. Символ $$\Gamma_{j,k}$$ определяет пару (символ, записанный в $$k$$ -й ячейке после $$j$$ тактов работы; состояние управляющего устройства после $$j$$ тактов работы, если головка находится над $$k$$ -й ячейкой, в противном случае второй элемент пары — $$\emptyset$$ ). Для простоты также считаем, что если вычисление заканчивается при некотором входе за $$T'<T$$ тактов, то строки c номерами, большими $$T'$$, повторяют строку с номером $$T'$$.
Построить схему, вычисляющую значения предиката на словах длины $$n$$, можно следующим образом. Состояние каждой клетки таблицы можно закодировать конечным (не зависящим от $$n$$ ) числом булевых переменных. Имеются локальные правила согласования, т.е. состояние каждой клетки $$\Gamma$$ в строке ниже нулевой однозначно определяется состояниями клеток в предыдущей строке, лежащих непосредственно над данной ( $$\Gamma'$$ ), левее данной ( $$\Gamma'_л$$ ) и правее данной ( $$\Gamma'_п$$ ). Каждая переменная, кодирующая состояние клетки $$\Gamma$$, есть функция от переменных, кодирующих состояния клеток $$\Gamma'_л$$, $$\Gamma'$$, $$\Gamma'_п$$. Все эти функции могут быть вычислены схемами конечного размера. Объединяя эти схемы, получим схему, вычисляющую все переменные, кодирующие состояния клеток таблицы; размер этой схемы будет $$O(ST)=O(n^{O(1)})$$.
Осталось заметить, что переменные, кодирующие часть клеток нулевой строки, определяются входным словом, а переменные, кодирующие остальные клетки нулевой строки, являются константами. Чтобы узнать результат вычисления, нужно определить символ, записанный в нулевой ячейке ленты в конце вычисления. Без ограничения общности можно считать, что состояния клеток таблицы кодируются так, что одна из кодирующих переменных равна 1 только в том случае, когда в ячейке записана 1. Тогда значение этой переменной для кода $$\Gamma_{T,0}$$ и будет результатом вычисления.
Замечание 1.1. Класс $$P/poly$$ шире класса $$P$$. Любой функции от натурального аргумента $$\varphi(n)$$ со значениями в $$\cb$$ можно сопоставить предикат $$f_\varphi$$ по правилу $$f_\varphi(x)=\varphi(|x|)$$, где $$|x|$$ обозначает длину слова $$x$$. Ограничение такого предиката на слова длины $$n$$ тождественно равно 0 или 1 (в зависимости от $$n$$ ). Схемная сложность таких функций ограничена константой. Поэтому все такие предикаты по определению принадлежат P/poly, хотя среди них есть и неразрешимые предикаты.
Справедливо следующее усиление теоремы.
Теорема 1.3. $$f$$ принадлежит $$\P$$ тогда и только тогда, когда
$$f\in P/poly$$
существует МТ, которая по числу $$n$$ за время $$\poly(n)$$ строит схему вычисления $$f_n$$.
Доказательство. $$\Longrightarrow$$ Данное в доказательстве теоремы 1.2. описание нетрудно превратить в МТ, которая строит схему вычисления $$f_n$$ за полиномиальное по $$n$$ время (схема $$f_n$$ имеет простую структуру: каждая переменная связана с предыдущими одними и теми же правилами согласования).
$$\Longleftarrow$$ Столь же просто. Вычисляем размер входного слова. Затем строим по этому размеру схему $$S_{|x|}$$ вычисления $$f_{|x|}$$, используя указанную в условии 2 машину. После этого вычисляем $$S_{|x|}(x)$$ на машине, которая по описанию схемы и значениям входных переменных вычисляет значение схемы за полиномиальное от длины входа время.
Задачи
Постройте машину Тьюринга, которая записывает входное двоичное слово в обратном порядке.
Постройте машину Тьюринга, которая складывает два числа, записанные в двоичной системе. Для определенности считайте, что записи чисел разделены специальным символом алфавита " $$+$$ ".
Докажите, что не существует алгоритма, который по машине Тьюринга и входу определяет, остановится ли она на этом входе.
Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.
Пусть $$T(n)$$ — максимальное время, которое может пройти до остановки машины Тьюринга с $$n$$ состояниями и $$n$$ символами алфавита, если ее запустить на пустой ленте. Докажите, что функция $$T(n)$$ растет быстрее любой вычислимой всюду определенной функции $$b(n)$$, то есть $$\lim [T(n)/b(n)]=+\infty$$.
Набор элементарных инструкций у описанных выше машин Тьюринга крайне беден. Имеются разнообразные их обобщения, например, многоленточные машины Тьюринга. В отличие от описанной выше, такая МТ имеет несколько (конечное множество) лент, каждая со своей головкой, управляющему устройству доступны символы, находящиеся в ячейках, на которых расположены головки лент. Выделены две ленты: входная, с которой разрешается только читать символы, и выходная, на которую разрешается только писать символы. Остальные ленты называются рабочими. Многоленточная машина называется $$k$$ -ленточной, если у нее $$k$$ рабочих лент. Действие за такт работы состоит в изменении состояния управляющего устройства, изменении символов в ячейках под головками и изменении положений головок на лентах (каждая головка сдвигается не более, чем на одну позицию). Это действие однозначно определяется состоянием управляющего устройства и набором символов в ячейках под головками. Если действие выполнить нельзя, машина останавливается.
В начале работы многоленточной машины Тьюринга все ленты пусты, кроме входной, на которой записан вход. Результат работы машины — состояние выходной ленты в конце работы.
Если интересоваться сложностью алгоритмов с точностью до полиномиально ограниченного множителя, многоленточные машины ничего не добавляют по сравнению с описанными выше машинами с единственной лентой.
Докажите, что двухленточную машину Тьюринга, работающую за время $$T(n)\ge n$$ на входах длины $$n$$, можно моделировать на машине с единственной лентой за время $$O(T^2(n))$$.
Докажите, что трехленточную машину Тьюринга, работающую за время $$T(n)\ge n$$ на входах длины $$n$$, можно моделировать на двухленточной за время $$O(T(n)\log T(n))$$.
Пусть $$M$$ — машина Тьюринга с единственной лентой, которая копирует входное слово (приписывая его копию справа от самого слова). Пусть $$T(n)$$ — максимальное время ее работы на входах длины $$n$$. Докажите, что $$T(n)\ge \varepsilon n^2$$ для некоторого $$\varepsilon$$ и для всех $$n$$. Что можно сказать про $$T'(n)$$, которое есть минимальное время ее работы на входах длины $$n$$?
Рассмотрим язык программирования, в котором есть всего $$100$$ натуральных переменных, разрешенные операции — прибавление и вычитание $$1$$, разрешенная проверка — не равна ли переменная нулю. Разрешено использовать if-then-else и while, но рекурсия не разрешена. Докажите, что с помощью программ на таком языке программирования можно вычислять любую вычислимую функцию.
Постройте алгоритм, определяющий, является ли данный базис полным. Базисные функции заданы таблицами значений.
Пусть $$c_n$$ есть максимум сложности $$c(f)$$ по всем булевым функциям $$f$$ от $$n$$ переменных. Докажите, что $$1{,}99^n<c_n<2{,}01^n$$ при достаточно больших $$n$$.
Глубиной схемы называется максимальное число элементов на пути от входов к выходу. Покажите, что любую функцию можно вычислить схемой глубины не более $$3$$ из элементов $$\NOT$$ и из элементов $$\AND$$ и $$\OR$$ с произвольным числом входов.
Докажите, что если из схемы глубины $$O(\log n)$$, вычисляющей функцию $$f\colon\cb^n\to\cb^m$$, выбросить все несущественные присваивания, то полученная схема имеет полиномиальный по $$n+m$$ размер.
Постройте схему, которая сравнивает два $$n$$ -битовых числа и имеет размер $$O(n)$$, а глубину $$O(\log n)$$.
Постройте схему сложения двух $$n$$ -битовых чисел размера $$O(n)$$.
Тот же вопрос, если дополнительно потребовать, чтобы глубина схемы была $$O(\log n)$$.
Функция $$\MAJ\colon \cb^n\to \cb$$ равна 1 на двоичных словах, в которых число единиц больше числа нулей, и 0 — на остальных словах. Постройте схему, вычисляющую эту функцию, размер схемы должен быть линеен по $$n$$, глубина — $$O(\log n\log\log n)$$.
Постройте схему размера $$\poly(n)$$ и глубины $$O(\log^2n)$$, которая проверяет, связаны ли путем две вершины в графе. Граф на $$m$$ вершинах, которые помечены числами от 1 до $$m$$, задается $$n=m(m-1)/2$$ булевыми переменными. Переменная $$x_{ij}$$, где $$i<j$$, определяет, есть ли в графе ребро, соединяющее вершины $$i$$ и $$j$$.
Пусть схема глубины $$3$$ из элементов $$\NOT$$ и из элементов $$\AND$$ и $$\OR$$ с произвольным числом входов вычисляет сложение $$n$$ битов по модулю $$2$$ (функция $$\PARITY$$ ). Покажите, что размер схемы не меньше $$c^n$$ для некоторого $$c>1$$.
Пусть $$f_1,f_2,\dots$$ — последовательность булевых функций от $$1,2,\dots$$ аргументов. Покажите, что следующие два свойства равносильны:
существует последовательность вычисляющих эти функции формул, размер которых не превосходит полинома от $$n$$ ;
существует последовательность вычисляющих эти функции схем глубины $$O(\log n)$$ из элементов $$\NOT$$, $$\AND$$ и $$\OR$$ (с двумя входами).
Докажите, что существует разрешимый предикат, который принадлежит $$P/poly$$, но не принадлежит $$P$$.
Неформально алгоритм — это однозначно определенная совокупность инструкций по преобразованию исходных данных в результат, причем все инструкции элементарны, т.е. при их выполнении "нам придется только механически следовать предписаниям, как если бы мы были роботами: от нас не потребуется ни понимания, ни искусства, ни изобретательности" [5, с. 270]. Формализовать это понятие можно различными способами.
Обычно подразумевается, что каждый алгоритм решает какую-то вычислительную задачу. С формальной точки зрения, вычислительная задача - это функция
F: входные данные -> результат,
Что такое "входные данные" и "результат"? Рассмотрим, например, задачу об умножении двух многочленов с целыми коэффициентами. Тогда входные данные - это пара многочленов. Проблема в том, как записать эти многочлены, чтобы их можно было ввести в компьютер. Машины Тьюринга, которые мы рассматриваем ниже, понимают лишь конечные последовательности символов (слова) из некоторого конечного множества A, называемого внешним алфавитом. Поэтому строгая формулировка вычислительной задачи должна включать в себя алфавит и способ кодировки входных данных. Например, можно записать пару многочленов с использованием 10 цифр, символа переменной x, знаков +, -, * и скобок: (x**2-5)(-4*x+1). В другой кодировке коэффициенты записываются в двоичной системе счисления и перечисляются через запятую; два многочлена разделяются звездочкой: 1, 0, -101* -100, 1. Таким образом, мы имеем две различные вычислительные задачи. С практической точки зрения, обе задачи эквивалентны, поскольку перевод из одной кодировки в другую осуществляется с помощью полиномиального алгоритма. Пока определения полиномального алгоритма у нас нет, давайте будем формалистами: вычислительная задача - это частичнаяПод частичной функцией на множестве X здесь и далее понимается функция, область определения которой содержится в X. функция F: A* -> A* (где A* обозначает множество конечных слов в алфавите $$A$$ ). Потом мы позволим себе некоторую вольность и будем говорить о задаче умножения многочленов или разложения целого числа на множители, имея ввиду, что все разумные кодировки эквивалентны (т.е. переводятся друг в друга при помощи полиномиальных алгоритмов). Однако нужно помнить, что не всякая кодировка является "разумной". Нехорошо, например, представлять натуральное число n набором из n звездочек, потому что длина такой записи экспоненциально велика по сравнению с двоичной или десятичной записью. Заметим также, что в некоторых задачах нет хорошего выбора "разумной" кодировки, в таких случаях (они нам не встретятся) необходимо указывать кодировку всякий раз, когда формулируется задача.
Теперь дадим формальное определение алгоритма.
Машины Тьюринга.
Машина Тьюринга (сокращенно МТ) однозначно задается указанием набора $$(\cal S, \_, \cal A, \cal Q, q_{0}, \delta)$$, где $$\cal S$$, $$\cal A$$, $$\cal Q$$ — конечные множества, причем $$\cal A\subset\cal S$$ ; $$\_$$ — некоторый элемент $$\cal S\setminus \cal A$$ ; $$q_{0}$$ — некоторый элемент $$\cal Q$$, а $$\delta$$ — некоторая (частичная, вообще говоря) функция из $$\cal Q\times\cal S$$ в $$\cal Q\times\cal S\times\{-1,0,1\}$$.
Составляющие части МТ называются так:
$$\cal S$$ — алфавит,
$$\_$$ — пустой символ (или пробел),
$$\cal A$$ — внешний алфавит,
$$\cal Q$$ — множество состояний управляющего устройства,
$$q_{0}$$ — начальное состояние,
$$\delta$$ — функция переходов.
Состояние МТ задается тройкой $$(\sigma,p,q)$$, где $$\sigma$$ — бесконечное слово в алфавите $$\cal S$$, т.е. произвольная последовательность $$s_0,\dots, s_n,\dots$$ элементов $$\cal S$$ ; $$p$$ — неотрицательное целое число; $$q\in\cal Q$$. Символы слова $$\sigma$$ будем, как это принято, представлять записанными на ленте, разбитой на ячейки, по ячейке на символ. На ленте также имеется головка, которая расположена над ячейкой с номером $$p$$. Наглядно это изображается так:
Помимо ленты машина Тьюринга имеет управляющее устройство, состояние которого задается элементом $$q$$ множества $$\cal Q$$.
Состояния МТ меняются дискретно. За один такт работы управляющее устройство выполняет следующие действия (полагаем, что МТ находится в состоянии $$(\sigma,p,q)$$ ):
читает символ, находящийся под головкой (т.е. определяет $$s_p$$ );
вычисляет значение функции переходов: $$\delta(q,s_p)=(q',s,\Delta p)$$ (если функция переходов на паре $$(q,s_p)$$ не определена, то останавливает машину Тьюринга);
записывает на ленту в ячейку $$p$$ символ $$s$$, сдвигает головку на $$\Delta p$$ и переходит в состояние $$q'$$ (другими словами, новое состояние машины задается тройкой $$((s_0,\dots,s_{p-1},s,s_{p+1},\dots), p+\Delta p,q')$$ );
если $$p+\Delta p<0$$, то останавливает машину.
Пожалуй, всякий согласится, что эти действия не требуют ни понимания, ни искусства, ни изобретательности.
Работа машины Тьюринга будет всегда начинаться из состояния $$(\alpha\_\dots,0,q_0)$$, где за конечным словом $$\alpha$$, состоящим из символов внешнего алфавита (множество таких слов обозначается $$\cal A^*$$ ), следует бесконечное слово, целиком состоящее из пустых символов. Слово $$\alpha$$ будем называть входом МТ. В любой момент времени слово, записанное на ленте, однозначно записывается в виде $$\sigma\_\dots$$, где последний символ слова $$\sigma$$ — не пустой, а за ним идут только пустые символы. Будем называть слово $$\sigma$$ используемой частью ленты.
Выполняя один такт работы за другим, машина Тьюринга порождает последовательность состояний $$(\sigma_0,0,q_0), \,(\sigma_1,p_1,q_1), \, (\sigma_2,p_2,q_2),\,\dots$$
Если МТ останавливается, используемая часть ленты в достигнутом перед остановкой состоянии называется результатом работы МТ.
Вычислимые функции и разрешимые предикаты.
Каждая машина Тьюринга $$М$$ вычисляет частичную функцию $$\ph_М$$ из $$\cal A^*$$ в $$\cal A^*$$, отображающую вход $$\alpha$$ в результат работы МТ на входе $$\alpha$$ при условии, что результат работы является словом во внешнем алфавите. Для входов, на которых машина не останавливается или результат содержит символы из $$\cal S\setminus\cal A$$, функция $$\ph_М$$ не определена. Из определения ясно, что любая МТ вычисляет ровно одну функцию (быть может, нигде не определенную).
Определение 1.1 Частичная функция $$f$$ из $$\cal A^*$$ в $$\cal A^*$$ называется вычислимой, если существует машина Тьюринга $$М$$, для которой $$\ph_М=f$$. При этом будем говорить, что $$f$$ вычислима на $$М$$.
Не все функции вычислимы. Это ясно из сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счетное множество). Более интересные примеры см. в задачах 1.3-1.5.
Под предикатом будем понимать некоторое условие, которое выполняется (предикат истинен) или не выполняется (предикат ложен) для каждого слова из $$\cal A^*$$. Определенные таким образом, предикаты легко отождествляются с языками (подмножествами слов в $$\cal A^*$$ ) — предикату соответствует множество слов, на которых он истинен. Каждому предикату сопоставим характеристическую функцию, которая равна 1 на множестве слов, для которых предикат истинен, и равна 0 на множестве слов, для которых предикат ложен. Мы будем обозначать характеристическую функцию так же, как и сам предикат. Предикат разрешим, если его характеристическая функция вычислима. О машине Тьюринга, вычисляющей характеристическую функцию предиката, будем говорить, что она дает ответ ("да" или "нет") на вопрос "истинно ли значение предиката на входе $$\alpha$$?"
Понятия вычислимой функции и разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных.
Пусть $$\cal A$$ — некоторый алфавит, а $$n$$ — натуральное число. Пусть $$M$$ — машина Тьюринга с внешним алфавитом $$\cal A\cup\{\#\}$$. Построим частичную функцию $$\ph_{M,n}$$ из $$(\cal A^*)^n$$ в $$\cal A^*$$ так: $$\ph_{M,n}(\alpha_1,\dots,\alpha_n)=y$$, если результат работы машины $$M$$ на входе $$\alpha_1\#\alpha_2\#\dots\#\alpha_n\#$$ совпадает со словом $$y$$. Если машина не останавливается или на ленте записано что-нибудь не то (например, символы не из алфавита $$\cal A$$ и т.п.), то $$\ph_{M,n}(\alpha_1,\dots,\alpha_n)$$ не определена.
Определение 1.2. Частичная функция $$f$$ из $$(\cal A^*)^n$$ в $$\cal A^*$$ называется вычислимой, если существует машина Тьюринга $$М$$, для которой $$\ph_{М,n}=f$$.
Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима.
Нас будут интересовать ресурсы, требующиеся для вычислений. Два важнейших ресурса — время и память. Будем говорить, что машина Тьюринга $$M$$ работает за время $$T_М(n)$$, если максимальное (по всем входам длины $$n$$ ) количество тактов, которое проработает $$М$$ до остановки, равно $$T_М(n)$$. Аналогично, машина Тьюринга $$M$$ работает на памяти $$S_М(n)$$, если наиболее удаленное от начала ленты положение головки при вычислениях на входах длины $$n$$ равно $$S_М(n)$$.
Вычисления на машинах Тьюринга.
Очевидно, что МТ задает алгоритм в смысле приведенного выше неформального определения. Обратное утверждение называется тезисом Черча:
"любой алгоритм может быть реализован машиной Тьюринга"
Не вдаваясь в обсуждение тезиса Черча, заметим, что в настоящее время нет серьезных оснований подвергать его сомнению. Все известные в настоящее время алгоритмы реализуются машинами Тьюринга. Подробное изложение теории алгоритмов читатель может найти в книгах [1, 5, 6, 10, 13, 16, 17]. Мы же ограничимся краткими неформальными пояснениями приемов программирования на машинах Тьюринга.
Возможности машины Тьюринга при таком неформальном обсуждении — это возможности человека с ограниченной памятью, карандашом и ластиком, которому вручили неограниченной (бесконечной) толщины тетрадь. Страницы тетради имеют ограниченный размер (все возможные варианты заполнения страницы образуют алфавит МТ при строгом описании). На первых страницах тетради записано входное слово — по одному символу (из внешнего алфавита) на страницу. Человек может листать тетрадь, стирать символы, записывать новые. Заканчивается эта его деятельность тем, что он закрывает тетрадь (сдвиг головки влево в положении 0) и возвращает результат своей работы.
Представив себя в такой ситуации, легко сообразить, что можно, запоминая несколько символов, выполнять любые действия на ограниченном количестве подряд идущих страниц; можно ставить на страницах дополнительные пометки (ограниченное количество на каждой); можно листать тетрадь, пока не найдется нужная пометка; можно копировать символы на свободные страницы тетради. Свободные места на страницах можно также использовать для хранения вспомогательных слов произвольной длины (как и входное слово, они записываются по одному символу на страницу), над которыми может поработать другой человек (это называется "вызов подпрограммы"). В частности, эти вспомогательные слова позволяют поддерживать счетчики (целочисленные переменные). Используя счетчики, можно адресоваться к ячейкам памяти по их номеру.
Поскольку описание любой машины Тьюринга является конечным объектом, его можно закодировать словом в некотором алфавите. В нашей неформальной ситуации легко понять, что существует универсальная машина Тьюринга $$U$$, которая, получая на вход пару $$([М],x)$$, дает выход $$\ph_M(x)$$. Здесь через $$[М]$$ обозначено описание некоторой машины Тьюринга $$М$$. Действительно, предположим, что тетрадь начинается со страниц, где записаны инструкции по работе. Тогда выполнять эти инструкции можно следующим образом: пометим текущую страницу; пролистаем тетрадь до начального раздела, содержащего инструкции; найдем нужную инструкцию; вернемся назад и выполним ее.
Сложностные классы.
Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма.
Формализовать это понятие непросто. Принятый сейчас способ состоит в том, что выделяются классы тех функций или предикатов, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы.Принадлежность функции тому или иному сложностному классу служит удобной характеристикой возможностей ее эффективного вычисления, не связанной с конкретными реализациями алгоритмов.
Наиболее важные классы получаются, если накладывать ограничения на рост времени работы и/или используемой памяти в зависимости от длины входного слова. А наиболее важное различие между эффективными и неэффективными вычислениями задается функциями полиномиального роста. Функция $$f(n)$$ — полиномиального роста, если для некоторой константы $$d$$ при достаточно больших $$n$$ выполняется неравенство $$f(n)\leq n^d$$. В этом случае будем использовать обозначение $$f(n)=\poly(n)$$.
Определение 1.3. Предикат $$f$$ на множестве $$\cb^*$$ принадлежит классу $$\P$$ (и называется полиномиально вычислимым ), если его характеристическая функция вычислима на машине Тьюринга $$М$$, для которой $$T_М(n)=\poly(n)$$.
Определение 1.4. Предикат $$f$$ на множестве $$\cb^*$$ принадлежит классу $$\PSPACE$$, если его характеристическая функция вычислима на машине Тьюринга $$М$$, для которой $$S_М(n)=\poly(n)$$.
По аналогии с предикатами можно определить и функции, вычислимые за полиномиальное время, и функции, вычислимые на полиномиальной памяти. Для классов таких функций также используются обозначения $$P$$ и $$PSPACE$$, так что точный смысл этих обозначений нужно восстанавливать из контекста.
Схемы
Схема (булева) — это способ вычислить функцию $$f\colon\cb^n\double\to\cb^m$$. Помимо исходных переменных $$x_1,\dots, x_n$$, для которых вычисляется значение $$f$$, схема использует некоторое количество вспомогательных переменных $$y_1,\dots, y_s$$ и некоторый набор ( базис ) булевых (т.е. принимающих значения 0 или 1) функций $$\cal F$$. Схема $$S$$ в базисе $$\cal F$$ определяется последовательностью присваиваний $$Y_1,\dots, Y_s$$. Каждое присваивание $$Y_i$$ имеет вид $$y_i:=f_j(u_{k_1},\dots,u_{k_r})$$, где $$f_j(\cdot)\in\cal F$$, а переменная $$u_{k_p}$$ ( $$1\leq p\leq r$$ ) — это либо одна из исходных переменных $$x_t$$ ( $$1\leq t\leq n$$ ), либо вспомогательная переменная $$y_l$$ с меньшим номером ( $$1\leq l<i$$ ). Таким образом, для каждого набора значений исходных переменных последовательное выполнение присваиваний, входящих в схему, однозначно определяет значения всех вспомогательных переменных. Результатом вычисления считаются значения последних $$m$$ переменных $$y_{s-m+1},\dots,y_s$$.
Схема вычисляет функцию $$f$$, если для любых значений $$x_1,\dots,x_n$$ исходных переменных результатом вычисления является $$f(x_1,\dots,x_n)$$.
Схема называется формулой, если каждая вспомогательная переменная используется в правой части присваиваний только один раз. (Обычные математические формулы именно так задают последовательность присваиваний: "внутри" формул не принято использовать ссылки на их части или другие формулы.)
Схему можно также представлять в виде ориентированного ациклического графа, у которого вершины входной степени 0 ( входы ) помечены исходными переменными; остальные вершины ( функциональные элементы ) помечены функциями из базиса (при этом входная степень вершины должна совпадать с количеством аргументов ее пометки); ребра помечены числами, указывающими номера аргументов; вершины выходной степени 0 ( выходы ) помечены переменными, описывающими результат работы схемы. Вычисление на графе определяется индуктивно: как только известны значения всех вершин $$y_1,\dots,y_{k_v}$$, из которых ведут ребра в данную вершину $$v$$, вершина $$v$$ получает значение $$y_v\double=f_v(y_1,\dots,y_{k_v})$$, где $$f_v$$ — базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются на пути к выходным вершинам, так что они никак не влияют на результат вычисления.
Базис называется полным, если для любой булевой функции $$f$$ есть схема в этом базисе, вычисляющая $$f$$. Ясно, что в полном базисе можно вычислить произвольную функцию $$f\colon\cb^n\to\cb^m$$ (такую функцию можно представить как упорядоченный набор из $$m$$ булевых функций).
Булева функция может быть задана таблицей значений. Приведем таблицы значений для трех функций$$\NOT(x)=\neg x,\ \OR(x_1,x_2)= x_1\vee x_2,\ \AND(x_1,x_2)=x_1\wedge x_2$$
( отрицание, дизъюнкция, конъюнкция ), образующих полный базис, который будем считать стандартным. В дальнейшем имеются в виду схемы именно в этом базисе, если явно не указано что-либо иное.$$\begin{array}{c|cccc|cccc|c}
x\NOT\quad x_1x_2\OR\quad x_1x_2\AND\\
\cline{1-2}\cline{4-6}\cline{8-10} 01 \quad 000 \quad 000\\
10 \quad 011 \quad 010\\ \multicolumn{2}{c}{} \quad
101 \quad 100\\ \multicolumn{2}{c}{} \quad 111
\quad 111\\ \end{array}$$
Конъюнкция и дизъюнкция определяются для произвольного числа булевых переменных аналогичным образом: конъюнкция равна 1 только тогда, когда все аргументы равны 1, а дизъюнкция равна 0 только тогда, когда все аргументы равны 0. В стандартном базисе они очевидным образом вычисляются схемами (и даже формулами) размера $$n-1$$.
Теорема 1.1. Базис $$\{\NOT,\OR,\AND\}$$ — полный.
Доказательство. Литералом будем называть переменную или ее отрицание. Конъюнкцией литералов (это схема и даже формула) легко представить функцию $$\chi_u(x)$$, которая принимает значение 1 ровно один раз: при $$x=u$$. Если $$u_i=1$$, включаем в конъюнкцию переменную $$x_i$$, если $$u_i=0$$, то включаем в конъюнкцию $$\neg x_i$$. Произвольная функция $$f$$ может быть представлена в виде
$$f(x)=\bigvee_{u: f(u)=1}\chi_u(x).$$
В таком случае говорят, что $$f$$ представлена в дизъюнктивной нормальной форме (ДНФ), т.е. как дизъюнкция конъюнкций литераловДалее нам еще потребуется и конъюнктивная нормальная форма (КНФ) — конъюнкция дизъюнкций литералов.
Как уже говорилось, дизъюнкция нескольких переменных выражается формулой в стандартном базисе.
Размером схемы называется количество присваиваний в схеме. Минимальный размер схемы в базисе $$\cal F$$, вычисляющей функцию $$f$$, называется схемной сложностью функции $$f$$ в базисе $$\cal F$$ и обозначается $$c_\cal F(f)$$. Переход от одного полного конечного базиса к другому полному конечному базису меняет схемную сложность функций на множитель $$O(1)$$. Так что в асимптотических оценках выбор конкретного полного базиса неважен и поэтому будем использовать обозначение $$c(f)$$ для схемной сложности $$f$$ в конечном полном базисе.
Каждый предикат $$f$$ на множестве $$\cb^*$$ определяет последовательность булевых функций $$f_n\colon \cb^n\to\cb$$ следующим образом: $$f_n(x_1,x_2,\dots,x_n)= f(x_1x_2\dots x_n)$$, где справа стоит характеристическая функция предиката $$f$$.
Определение 1.5. Предикат $$f$$ принадлежит классу $$P/poly$$, если $$c(f_n)=\poly(n)$$.
Теорема 1.2. $$\P\subset P/poly$$.
Если МТ работает за полиномиальное время, то и память, которую она использует, ограничена полиномом. Поэтому весь процесс вычисления на входном слове $$x$$ длины $$n$$ можно представить таблицей вычисления размера $$T\times S$$, где $$T= \poly(n)$$, $$S= \poly(n)$$.
(рис 1.1) Строка с номером $$j$$ таблицы задает состояние МТ после $$j$$ тактов работы. Символы $$\Gamma_{j,k}$$, записанные в таблице, принадлежат алфавиту $$\cal S\times\{\emptyset\cup\cal Q\}$$. Символ $$\Gamma_{j,k}$$ определяет пару (символ, записанный в $$k$$ -й ячейке после $$j$$ тактов работы; состояние управляющего устройства после $$j$$ тактов работы, если головка находится над $$k$$ -й ячейкой, в противном случае второй элемент пары — $$\emptyset$$ ). Для простоты также считаем, что если вычисление заканчивается при некотором входе за $$T'<T$$ тактов, то строки c номерами, большими $$T'$$, повторяют строку с номером $$T'$$.
Построить схему, вычисляющую значения предиката на словах длины $$n$$, можно следующим образом. Состояние каждой клетки таблицы можно закодировать конечным (не зависящим от $$n$$ ) числом булевых переменных. Имеются локальные правила согласования, т.е. состояние каждой клетки $$\Gamma$$ в строке ниже нулевой однозначно определяется состояниями клеток в предыдущей строке, лежащих непосредственно над данной ( $$\Gamma'$$ ), левее данной ( $$\Gamma'_л$$ ) и правее данной ( $$\Gamma'_п$$ ). Каждая переменная, кодирующая состояние клетки $$\Gamma$$, есть функция от переменных, кодирующих состояния клеток $$\Gamma'_л$$, $$\Gamma'$$, $$\Gamma'_п$$. Все эти функции могут быть вычислены схемами конечного размера. Объединяя эти схемы, получим схему, вычисляющую все переменные, кодирующие состояния клеток таблицы; размер этой схемы будет $$O(ST)=O(n^{O(1)})$$.
Осталось заметить, что переменные, кодирующие часть клеток нулевой строки, определяются входным словом, а переменные, кодирующие остальные клетки нулевой строки, являются константами. Чтобы узнать результат вычисления, нужно определить символ, записанный в нулевой ячейке ленты в конце вычисления. Без ограничения общности можно считать, что состояния клеток таблицы кодируются так, что одна из кодирующих переменных равна 1 только в том случае, когда в ячейке записана 1. Тогда значение этой переменной для кода $$\Gamma_{T,0}$$ и будет результатом вычисления.
Замечание 1.1. Класс $$P/poly$$ шире класса $$P$$. Любой функции от натурального аргумента $$\varphi(n)$$ со значениями в $$\cb$$ можно сопоставить предикат $$f_\varphi$$ по правилу $$f_\varphi(x)=\varphi(|x|)$$, где $$|x|$$ обозначает длину слова $$x$$. Ограничение такого предиката на слова длины $$n$$ тождественно равно 0 или 1 (в зависимости от $$n$$ ). Схемная сложность таких функций ограничена константой. Поэтому все такие предикаты по определению принадлежат P/poly, хотя среди них есть и неразрешимые предикаты.
Справедливо следующее усиление теоремы.
Теорема 1.3. $$f$$ принадлежит $$\P$$ тогда и только тогда, когда
$$f\in P/poly$$
существует МТ, которая по числу $$n$$ за время $$\poly(n)$$ строит схему вычисления $$f_n$$.
Доказательство. $$\Longrightarrow$$ Данное в доказательстве теоремы 1.2. описание нетрудно превратить в МТ, которая строит схему вычисления $$f_n$$ за полиномиальное по $$n$$ время (схема $$f_n$$ имеет простую структуру: каждая переменная связана с предыдущими одними и теми же правилами согласования).
$$\Longleftarrow$$ Столь же просто. Вычисляем размер входного слова. Затем строим по этому размеру схему $$S_{|x|}$$ вычисления $$f_{|x|}$$, используя указанную в условии 2 машину. После этого вычисляем $$S_{|x|}(x)$$ на машине, которая по описанию схемы и значениям входных переменных вычисляет значение схемы за полиномиальное от длины входа время.
Задачи
Постройте машину Тьюринга, которая записывает входное двоичное слово в обратном порядке.
Постройте машину Тьюринга, которая складывает два числа, записанные в двоичной системе. Для определенности считайте, что записи чисел разделены специальным символом алфавита " $$+$$ ".
Докажите, что не существует алгоритма, который по машине Тьюринга и входу определяет, остановится ли она на этом входе.
Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.
Пусть $$T(n)$$ — максимальное время, которое может пройти до остановки машины Тьюринга с $$n$$ состояниями и $$n$$ символами алфавита, если ее запустить на пустой ленте. Докажите, что функция $$T(n)$$ растет быстрее любой вычислимой всюду определенной функции $$b(n)$$, то есть $$\lim [T(n)/b(n)]=+\infty$$.
Набор элементарных инструкций у описанных выше машин Тьюринга крайне беден. Имеются разнообразные их обобщения, например, многоленточные машины Тьюринга. В отличие от описанной выше, такая МТ имеет несколько (конечное множество) лент, каждая со своей головкой, управляющему устройству доступны символы, находящиеся в ячейках, на которых расположены головки лент. Выделены две ленты: входная, с которой разрешается только читать символы, и выходная, на которую разрешается только писать символы. Остальные ленты называются рабочими. Многоленточная машина называется $$k$$ -ленточной, если у нее $$k$$ рабочих лент. Действие за такт работы состоит в изменении состояния управляющего устройства, изменении символов в ячейках под головками и изменении положений головок на лентах (каждая головка сдвигается не более, чем на одну позицию). Это действие однозначно определяется состоянием управляющего устройства и набором символов в ячейках под головками. Если действие выполнить нельзя, машина останавливается.
В начале работы многоленточной машины Тьюринга все ленты пусты, кроме входной, на которой записан вход. Результат работы машины — состояние выходной ленты в конце работы.
Если интересоваться сложностью алгоритмов с точностью до полиномиально ограниченного множителя, многоленточные машины ничего не добавляют по сравнению с описанными выше машинами с единственной лентой.
Докажите, что двухленточную машину Тьюринга, работающую за время $$T(n)\ge n$$ на входах длины $$n$$, можно моделировать на машине с единственной лентой за время $$O(T^2(n))$$.
Докажите, что трехленточную машину Тьюринга, работающую за время $$T(n)\ge n$$ на входах длины $$n$$, можно моделировать на двухленточной за время $$O(T(n)\log T(n))$$.
Пусть $$M$$ — машина Тьюринга с единственной лентой, которая копирует входное слово (приписывая его копию справа от самого слова). Пусть $$T(n)$$ — максимальное время ее работы на входах длины $$n$$. Докажите, что $$T(n)\ge \varepsilon n^2$$ для некоторого $$\varepsilon$$ и для всех $$n$$. Что можно сказать про $$T'(n)$$, которое есть минимальное время ее работы на входах длины $$n$$?
Рассмотрим язык программирования, в котором есть всего $$100$$ натуральных переменных, разрешенные операции — прибавление и вычитание $$1$$, разрешенная проверка — не равна ли переменная нулю. Разрешено использовать if-then-else и while, но рекурсия не разрешена. Докажите, что с помощью программ на таком языке программирования можно вычислять любую вычислимую функцию.
Постройте алгоритм, определяющий, является ли данный базис полным. Базисные функции заданы таблицами значений.
Пусть $$c_n$$ есть максимум сложности $$c(f)$$ по всем булевым функциям $$f$$ от $$n$$ переменных. Докажите, что $$1{,}99^n<c_n<2{,}01^n$$ при достаточно больших $$n$$.
Глубиной схемы называется максимальное число элементов на пути от входов к выходу. Покажите, что любую функцию можно вычислить схемой глубины не более $$3$$ из элементов $$\NOT$$ и из элементов $$\AND$$ и $$\OR$$ с произвольным числом входов.
Докажите, что если из схемы глубины $$O(\log n)$$, вычисляющей функцию $$f\colon\cb^n\to\cb^m$$, выбросить все несущественные присваивания, то полученная схема имеет полиномиальный по $$n+m$$ размер.
Постройте схему, которая сравнивает два $$n$$ -битовых числа и имеет размер $$O(n)$$, а глубину $$O(\log n)$$.
Постройте схему сложения двух $$n$$ -битовых чисел размера $$O(n)$$.
Тот же вопрос, если дополнительно потребовать, чтобы глубина схемы была $$O(\log n)$$.
Функция $$\MAJ\colon \cb^n\to \cb$$ равна 1 на двоичных словах, в которых число единиц больше числа нулей, и 0 — на остальных словах. Постройте схему, вычисляющую эту функцию, размер схемы должен быть линеен по $$n$$, глубина — $$O(\log n\log\log n)$$.
Постройте схему размера $$\poly(n)$$ и глубины $$O(\log^2n)$$, которая проверяет, связаны ли путем две вершины в графе. Граф на $$m$$ вершинах, которые помечены числами от 1 до $$m$$, задается $$n=m(m-1)/2$$ булевыми переменными. Переменная $$x_{ij}$$, где $$i<j$$, определяет, есть ли в графе ребро, соединяющее вершины $$i$$ и $$j$$.
Пусть схема глубины $$3$$ из элементов $$\NOT$$ и из элементов $$\AND$$ и $$\OR$$ с произвольным числом входов вычисляет сложение $$n$$ битов по модулю $$2$$ (функция $$\PARITY$$ ). Покажите, что размер схемы не меньше $$c^n$$ для некоторого $$c>1$$.
Пусть $$f_1,f_2,\dots$$ — последовательность булевых функций от $$1,2,\dots$$ аргументов. Покажите, что следующие два свойства равносильны:
существует последовательность вычисляющих эти функции формул, размер которых не превосходит полинома от $$n$$ ;
существует последовательность вычисляющих эти функции схем глубины $$O(\log n)$$ из элементов $$\NOT$$, $$\AND$$ и $$\OR$$ (с двумя входами).
Докажите, что существует разрешимый предикат, который принадлежит $$P/poly$$, но не принадлежит $$P$$.
