Cтраница 3
Эта статья стала широко известна и дала название описываемой области исследований. Было введено важное понятие меры сложности как времени вычислений на многоленточных машинах Тьюринга, и были доказаны теоремы об иерархии. [31]
Таким образом, это побуждает нас использовать простую модель, для которой временная сложность задач полиномиально связана с их сложностью на РАМ. В частности, модель, которую мы будем применять, а именно многоленточная машина Тьюринга, может потребовать ( / ( п)) 4 шагов х), чтобы сделать то, что РАМ при логарифмической весовой функции делает за / ( п) шагов, но не больше. Итак, временные сложности на РАМ и машинах Тьюринга, как мы увидим, полиномиально связаны. [32]
Функция o ( i) по машине Mi дает новую машину, которая проверяет, сколько ленты использует Мг -, и затем записывает число ячеек ленты в качестве выхода в подходящей ( скажем, двоичной) форме. При подходящих соглашениях о записи выхода то же самое верно для временных сигнализирующих многоленточных машин Тьюринга. Это наводит на мысль о том, что меры, у которых сигнализирующие служат границами сложности, собственных вычислений, заслуживают специального внимания. [33]
Класс языков, распознаваемых словарными распознающими алгоритмами за полиномиальное время, также инвариантен относительно широкого ряда изменений в классе алгоритмов. Например, любой язык, распознаваемый за время р ( -) на многоголовочной или многоленточной машине Тьюринга, распознаваем за время /) 2 ( -) на одноленточной машине Тьюринга. Таким образом, класс языков, распознаваемых за полиномиальное время на одноленточной машине Тьюринга, тождествен классу, распознаваемому на, казалось бы, более мощных многоголовочных или многоленточных машинах Тьюринга. Подобные замечания применимы к машинам со случайным доступом. [34]
В [2] было показано, что каждую недетерминированную t ( n) - ограниченную ( сверху) по времени многоленточную машину Тьюринга ( ТМ) можно промоделировать недетерминированной также i ( n) - ограниченной по времени двухленточной ТМ. ТМ одно-ленточной альтернирующей ТМ возможно без потери времени. [35]
Оценку Mm ( N) сложности способа Vm можно теперь получить, используя значение Mm ( s) и употребляя оценку 0 ( s) для сложения s - разрядных чисел. В логической сети числам ( о, х отвечают специальные блоки. При использовании многоленточной машины Тьюринга они предварительно вычисляются. [36]
Если глубина каждого направленного ациклического графа с п ребрами может быть приведена к log n удалением только о ( п) ребер, то недетерминированные многоленточные машины Тьюринга за линейное время могут распознавать языки, не распознаваемые детерминированными многоленточными машинами Тьюринга за такое же время. Для некоторых графов уменьшение глубины до log п требует удаления Q ( / z / log log п) ребер. Дается теоретико-графовое условие того, что забывчивость ( obliviousness) уменьшает мощность многоленточных машин Тьюринга. [37]
Так как D обязательно останавливается независимо от данного входного слова, то она распознает некоторое множество входных слов, которое мы обозначим R. Покажем теперь, что R не Т ( п) - распознаваемо. Действительно, предположим, что R является Т ( п) - распознаваемым некоторой многоленточной машиной Тьюринга. Тогда в соответствии с теоремой б оно должно быть Т ( п) log Т ( п) - распознаваемо некоторой двуленточной машиной Тьюринга Mk. Если целое число k, представленное в двоичной форме, подается машине Mk в качестве входного слова длины п, то вычисление потребует самое большее Т ( п) log Т ( п) операций. Оценим теперь число шагов, необходимое для имитации того же самого вычисления на машине D. Определение длины входного слова потребует самое большее п операций, а переписывание входного слова требует не больше чем а / г операций, где а есть некоторая константа. [38]
Мы предлагаем новый подход, который позволяет разбить цену диагонализации любого класса сложности на цену моделирования и цену параллельных вычислений. Из этой общей формулировки мы можем извлечь результаты о классах сложности для специальных мер, если мы знаем, насколько трудно при данной мере моделировать вычисления и выполнять их параллельно. Это иллюстрируется на трех довольно несхожих результатах для классов сложности вычислений на машинах Тьюринга с ограничением на емкость ленты, а также для вычислений на одноленточных и многоленточных машинах Тьюринга с ограничением на время вычисления. [39]
Класс языков, распознаваемых словарными распознающими алгоритмами за полиномиальное время, также инвариантен относительно широкого ряда изменений в классе алгоритмов. Например, любой язык, распознаваемый за время р ( -) на многоголовочной или многоленточной машине Тьюринга, распознаваем за время /) 2 ( -) на одноленточной машине Тьюринга. Таким образом, класс языков, распознаваемых за полиномиальное время на одноленточной машине Тьюринга, тождествен классу, распознаваемому на, казалось бы, более мощных многоголовочных или многоленточных машинах Тьюринга. Подобные замечания применимы к машинам со случайным доступом. [40]
Поскольку наша интерпретация вычислений в реальное время дана в терминах С-вычислений, мы предполагаем вникнуть в сущность вычислений в реальное время с помощью детального изучения С-машин. Хотя предположения относительно входа С-машин и дают большие возможности, желательно устраивать дело так, чтобы автомат выдавал на выходе в 1 - й раз 1 в том и только том случае, когда прошло ровно f ( i) моментов времени; для этого достаточно подавать на вход последовательность единиц. В этом случае вход просто служит метрономом. Грубо говоря, мы хотим, чтобы М была многоленточной машиной Тьюринга с одним двоичным входом и одним двоичным выходом. [41]
Школьный метод требует О ( / г2) битовых операций для умножения двух ft - разрядных чисел. В 1962 г. Карацуба и Офман [41] опубликовали метод, требующий всего О ( ft1 59) шагов. Вскоре после этого Тоом [84] показал, как построить булеву схему сложности О ( ft1 8) для произвольно малого е0, выполняющую умножение. Я был в это время студентом старшего курса в Гарварде, и, вдохновленный вопросом Кобэма: Сложнее ли умножение, чем сложение. Q ( ft2) шагов на многоленточной машине Тьюринга. Статья Тоома сильно удивила меня. С помощью Стола Аандераа [22] я показал, что умножение требует Q ( ft logft / ( loglog ft) 2) шагов машины Тьюринга1) при вычислении on line. Я отметил в сво - Й диссертации, что метод Тоома может быть приспособлен к многоленточным машинам Тьюринга, с тем чтобы выполнить умножение за О ( п1 л) шагов, - то, что, я уверен. Тоома не удивило бы. [42]
МОА расширяется за счет бесконечного числа состояний устройства управления, но с тем ограничением, что лишь конечное число из них может читать входную ленту. Оракул, даже нерекурсивный, можно вызывать такой машиной, чтобы читать последовательность ячеек памяти и помещать результат применения его оракульной функции в некоторую другую последовательность ячеек. Вся процедура займет то же число шагов, что и доступ к этим ячейкам, в силу чего доказательства становятся неэффективными. Простой пример, который подчеркивает важность ограничения на темп работы машины для нашего доказательства, - многоленточная машина Тьюринга с оракулом для выполнения автономного умножения в линейное время. [43]
Школьный метод требует О ( / г2) битовых операций для умножения двух ft - разрядных чисел. В 1962 г. Карацуба и Офман [41] опубликовали метод, требующий всего О ( ft1 59) шагов. Вскоре после этого Тоом [84] показал, как построить булеву схему сложности О ( ft1 8) для произвольно малого е0, выполняющую умножение. Я был в это время студентом старшего курса в Гарварде, и, вдохновленный вопросом Кобэма: Сложнее ли умножение, чем сложение. Q ( ft2) шагов на многоленточной машине Тьюринга. Статья Тоома сильно удивила меня. С помощью Стола Аандераа [22] я показал, что умножение требует Q ( ft logft / ( loglog ft) 2) шагов машины Тьюринга1) при вычислении on line. Я отметил в сво - Й диссертации, что метод Тоома может быть приспособлен к многоленточным машинам Тьюринга, с тем чтобы выполнить умножение за О ( п1 л) шагов, - то, что, я уверен. Тоома не удивило бы. [44]