Cтраница 1
Хартманис и Стирнз [2] показали, что одноленточная машина может моделировать работу - ленточной машины за время, не большее, чем квадрат времени работы - ленточной машины. Хенни [3] показал, что имеются случаи, в которых доведение числа лент от двух до одной в действительности требует квадрата времени вычисления. Таким образом, моделирование может быть произведено достаточно эффективно только с использованием более чем одной ленты. [1]
Стирнз, Хартманис и Льюис [14] заметили, что при изучении произвольного класса пространственной сложности Cs в случае ТМ достаточно рассматривать одно-ленточные ТМ. [2]
Имеется перевод: Хартманис Дж, Стирнз Р, О вычислительной сложности алгоритмов. [3]
Эта статья продолжает исследование ( начало которому положили Хартманис и Стирнз [1]) вычислительной сложности двоичных последовательностей, порождаемых многоленточными машинами Тьюринга. На ленте могут быть символы лишь из конечного множества, а управляющее устройство может находиться только в конечном числе внутренних состояний. Машинная операция полностью определяется состоянием процессора и символами, находящимися под головками на лентах, и состоит в печатании символов в каждой из ячеек под головками, сдвигании каждой из лент самое большее на одну ячейку в любом направлении и изменении состояния процессора. Исходя из некоторого начального состояния и набора пустых лент, машина порождает двоичную последовательность на специальной односторонней выходной ленте. [4]
Мы кратко повторяем хорошо известные факты о вычислениях на машине Тьюринга с ограниченной зоной, впервые установленные Хартманисом, Стирнзом и Льюисом. [5]
Продолжение новой серии кибернетических сборников, публикация которой начата издательством Мир в 1965 г. В данном выпуске большой интерес представит обзорная статья известных ученых Хартманиса и Хопкрофта по теории сложности вычислений, а также статья Сэлтона, в которой излагаются некоторые новые результаты из области информационного поиска. [6]
Работы Хартманиса и Стирнза [2, 3] показывают, что уменьшение размерности ленты машины Тьюринга никогда не требует больше чем квадрата обычного времени вычисления. [7]
Множество входных последовательностей, распознаваемых М2, обозначим через В. Согласно Хартманису и Стирнзу [2, 3], переход от двумерной реализации к одномерной требует самое большее квадрата времени вычисления. Теперь мы желаем найти нижнюю границу времени вычисления одномерной машины, которая распознает В. [8]
Итак, для приведенного примера время наилучшего вычисления, которого можно достичь в случае одноленточной машины с записью на ленте, пропорционально квадрату времени наилучшего вычисления, которого можно достичь в случае двулен-точной машины. С другой стороны, из работы Хартманиса и Стирнза [2] известно, что если данная двуленточная машина завершает свои вычисления за Т2 ( п) единиц времени, то должна существовать одноленточная машина, которая завершает свои вычисления за время C [ Ti ( n) ] 2, где С-константа. Другими словами, переходя от двуленточной машины к одноленточной, никогда не нужно требовать более чем квадрата времени вычисления. Однако теперь мы имеем пример, в котором квадрат необходим. Таким образом, закон квадрата Хартманиса - Стирнза не может быть, вообще говоря, улучшен. [9]
Первая попытка аксиоматического подхода к измерению трудности вычислений была сделана Рабином [3, 4], который аксиоматизировал понятие меры на доказательствах и длины вычисления функции и получил некоторые начальные результаты для этих мер. Первое систематическое исследование одной специфической меры сложности вычислений и изучение соответствующих классов сложности принадлежит Хартманису и Стирнзу [5, 6], которые дали также название сложность вычислений этой новой области исследований. В докладе Кобхэма [7] обсуждалась важность исследования количественных аспектов вычисления и приводились некоторые дальнейшие, результаты. [10]
Комбинаторный аспект в логическом проектировании связан, в основном, с поиском оптимальных вариантов кодирования состояний, входных и выходных сигналов автомата и приводит к задачам декомпозиции сложных автоматов на более простые по тем или иным критериям. Среди работ, которые освещают вопросы комбинаторного порядка в логическом проектировании автоматов, необходимо отметить работы Хартманиса, Стернза, А. [11]
К сожалению, я-ленточная машина, распознающая множество А за время 2L ( /), не всегда может быть заменена какой-либо m - ленточной машиной, работающей в реальном масштабе времени. Однако если такое сжатие г шагов в один шаг достаточно, чтобы ускорить машину Тьюринга до реального масштаба времени, то алгоритм Хартманиса и Стирнза [ 5, теорема 2 ] дает эффективный метод этого ускорения. В частности, если / г-ленточная машина Тьюринга воспринимает входную последовательность с постоянной скоростью, этот алгоритм дает нам эквивалентную гс - МРВ. Покажем теперь, что машина, определяющая V - l ( A) для А из R, относится к этому специальному виду. [12]
Первая часть теоремы доказывается легко. Читатель может восстановить доказательство самостоятельно, рассмотрев последовательность покрытий Ch, где Ck есть совокупность всех подмножеств из X, содержащих менее k состояний, или воспользовавшись леммой 7.5 из работы Хартманиса и Стирнза [ 1, с. Для того чтобы доказать более трудную часть теоремы, нужно, получить условия, при которых можно применить лемму о ретракте, позволяющую исследовать группы перестановок. Из-за этого приходится вступить на довольно сложный путь выбора покрытий. Разумеется, доказательство следует вести по индукции, но на каждом стандартном шаге ее возникают серьезные технические трудности и поэтому приходится прибегать к искусственным методам. [13]
Другой их основной результат состоял в том, что для любой вычислимой монотонной функции Т множество ST является рекурсивно перечислимым. Поскольку множество всех бесконечных вычислимых двоичных последовательностей не является рекурсивно перечислимым, тЬ отсюда следует, что существует бесконечно много различных классов сложности. Хартманис и Стирнз показали далее, что бесконечное частично упорядоченное множество классов сложности имеет бесконечное линейное упорядоченное подмножество. Этот результат был получен с использованием диагонального метода и того факта, что вычисление, производимое за Т ( п) операций на некоторой многоленточной машине, можно осуществить за ( Г ( п)) 2 операций на одноленточной машине Тьюринга. [14]
В главе 4 излагается доказательство Зейгера теоремы Крона - Роудза о декомпозиции автомата. Оно основывается на аппарате теории покрытий. Возможно, это доказательство будет ближе читателям, знакомым с работами Хартманиса и Стирнза по декомпозиции автоматов. [15]