В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 7
Текст из файла (страница 7)
Однако здесь опять можно применить метод перехода от задачи распознавания к вычислению алгебраического выражения, чтобы испольэовать силу алгебры [1]. Теорема 3.6. 2?яя сюбозо фиксировонново т > 2 существует ояеоритм для ответа но вопрос "Г(хь .. х„) й У(В )?" с бипювоб свохсиостью 0(Ф 1обз?у). ' Замечание. Константа зависит от т (растет с ростом т).
Яоиозотельство. Пусть йь йэ,..., й — произвольные наборы, где ссу = (оь оз,..., оа), н цУсть Да дпк пуонэвопьного нзбоуа й обозначает такую логическую переменную, что д» = "истина" тогда и только тогда, когда Дй) = 1. Тогда по определению Дхь...,х„) ф Е с=о «=о Зйь..., й (А„",(йь..., й )Зс(1(й1) = 1)3с... Зс(У(й ) = 1)) 4=ь ~/ на(<~1 ° ~ ои)Ч»Ь ' ° ' Ча ао...,а ~/ Е ( '". Г).В (4" Г) " Е-(.""-,.)ув, " у~.
аи А Определим функпию 1„(аь..., о ), где аз Е (О, 1), и переменные и следующим образом: (О, если В (оь...,а,„), г„,(аь.,,, ) = ~ (1, если В (а~,...,а ). О, если е = ложь, на 1, если д = истина. Легко видеть, что ~/ В (аз~,...,а~) ... В (а~,...,а„)да, °... 1в =истинами=ь аь...,а Т« =,~' Фе(й,',...,о, ) ... ~т(а,'„...,а„)иа,.... иа„> О. а«...,а Пусть Ь,' (о) = Ь,р(Ф) — наименьшее число арифметических операций, необходимых для вычисления Т„.
Обозначим Д й з ~-1) 71 Ми 1~'(Рь...,А~)=А (о~,",од) ... 1.а(о«-п . ~о«-~). Тогда Т« = ~~'~,~ г«(о~ . о~ )' . 'с«(сз«~ '"«)'оА „,' . о и А, д 71- 7 с~в (Рь .. 4в) ~~' ~пз(7ь... 7~в)оА, „' ' оА„,з„= А,... 3 Г«г —,т МдТ = Е " (д, ,д-) А -.Ф г«'. 7 )Фб, ° д) йт (А ° Рт)((оАд+ ьА Д(иА о+ иАд) . ' (од о+ил д)- А,...,А. — иАзиАз .... ид ~) = ~ ~г" (А,.,Р )оАгА ' . 'оД А,....в 1««(~3ь -, От)~~>АюА ' ' юд А,- Ф где о,1 —— и- + из,, а юз = иА .
Сведи задачу с параметром и к 2 таким же подзадачам с параметром и — 1. Отсюда й' (и) < 2Ь', (и — 1) + 2" '+ 1, поскольку для вычисления всех е- достаточно 2" " сложений и одного вычи- Р тания достаточно для вычисления Т„после решения двух подзадач. Переходя к йГ, имеем Е', (йГ) = 21,р( з ) + 0(Ф). Отсюда по теореме 2.4 о рекуррентном неравенстве получаем б р(Ж) = 0(М1обМ) (в этой теореме имеем а = 2,с = 2,а = 1). Отметим, что исходная задача была для ие Е 10, Ц.
Однако в подзадачах переменные могут быть произвольными натуральными числами. Переход к подзадачам делается п — 1 раз. При каждом переходе разрядность переменных увеличивается не более, чем на 1, поэтому в подзадачах все числа имеют длину не более о + 1. При и = 0 получаются подзадачи вычисления Те вила Те = з. з. з з ... з = г~, в которых образуются числа длины ( (гл(п + 1). При переходе к задаче из подзадач длина чисел увеличивается не более, чем на 1, поэтому все числа в алгоритме имеют длину не более гл(п + 1) + и < солзб л. Оледовательно, каждая арифметическая операция требует 0(лз) = 0(1ой~ Ю) битовых операций, откуда Ь(Л) 1 др(№~ ' 0(1оя Л) = 0(Л 1оя Ж).
'1еорема доказана. 4. Общая теория сложности задач Если мы хотим получать утверждения типа "для любых алгоритмов", то мы должны принять хакую-нибудь универсальную модель алгоритмов. Одной из таких моделей является машина Тьюринга. 4.1. Машины Тьюринга Машина Тьюринга М имеет потенциально бесконечкую ленту, разделенную на ячейки, и головку, хоторая в каждый (дискретный) момент времени 1 = О, 1, 2,... обозревает ровно одну ячейку. Задано некоторое конечное множество состояний Я = (до, оь..., ЧД, и машина в каждый момент времени находится ровно в 1 из этих состояний. Задав конечный ленточный 1рабочий) алфавит С = (се, сз,..., с„Д, где со = Л вЂ” пустой символ, и в каждый момент времени в каждой ячейке находится ровно 1 символ нз алфавита С, причем будем считать, что символы, отличные от Л, находятся лишь в конечном числе ячеек.
Ма шина М характеризуется ее программой, которая представляет собой конечный набор команд вида: с,дз — ~ с~д,Т, где с» Е С, сз Е С, о1 ч Я, д, Е Я, Т Е (Ь, Н,Я). На каждом такте машина М работает следующвм образом. Если головка обозревает ячейку, в которой находится символ с;, М находится в состояния е н в программе машины М есть команда с,е1 -~ сщ„Т, то символ в обозреваемой ячейке заменяется на см машина переходит в состояние о„и головка остается на месте, если Т = Я, нли сдвигается на 1 ячейку вправо или влево, если Т = В или Т = Ь. Палее машина переходит к следующему такту и повторяет этот процесс.
Если же в программе машины нет команды, в невой части которой стоит пара с,.е,, то машина останавливается. Мы будем рассматривать только детерминированные машины Тьюрннга, то есть такие, у которых в программе каждая пара с<~~ встречается в левых частях команд не более одного раза. В этом случае кажный шаг машины определяется однозначно. Определение. Если А — алфавит, то через А' будем обозначать множество всех (конечных) слов в алфавите А.
Пусть С вЂ” ленточный алфавит мюпивы М, Са = С 1 (Л) и пусть задан некоторый входной алфавит А, такой, что А С Со. Тогда мы будем считать, что мазпина М осуществляет преобразование ум: А" -~ Сз О (*), которое определяется следующим образом (здесь * в (*) трактуется как неопределенность). Пусть задано некоторое слово а = азаз... о„б А'. Разместим символы этого слова в последовательные ячейки ленты, а в остальные ячейки поместим й, поместим головку на ячевку, в которой стоит аь установим машину в начальное состояние о1 и начнем работу машины. Если после этого машина М будет работать бесконечно долго, то счвтаем, что ум(атаг...
а„) = ю Если машина М остановится и на ленте все символы равны Л или между символами алфавита Св будет встречатьгл Л, то также ~ом(агаг... а„) = в. Если же после остановки машины М все символгя алфавита Св на ленте стоят подряд, образуя слово 6, то чтм(а) = Ь. Тезис Тьюринга. Для любого алгоритамичесного преобразования ут: А' -т Со 0(т) суитестпвует машина Тьюринга М, осутцестпвляянцая преобразование у. 4.2. Сутнествование сложных задач Рассмотрим все машины Тьюринга, имеющие в ленточном алфавите символы Л и ). Пусть о+ = (О) 0 йт, где Ф вЂ” множество натуральных чисел. Будем представлять число й Е Я+ на ленте машвны в виде кода й Й ...
! Л, где количество ) равно Й + 1 (остальные символы на ленте Л). Набор (йь йг,..., Ь„) будем представлять в виде кода Л ~! ... ~ Л Й ... ~ Л... Л ~) ... ) Л, где в первом массиве 61 + 1 символов ~, во втором ля+1 и т.д. Применяя машину М к коду числа или набора, будем помещать головку на самый первый символ ~ и устанавливать машану М в ее начальное состояние дь Оцределенже. Пля шобой машины Тьюринга М и любого натурального числа и будем считать, что машина М вычисляет функцию у(хг,хг,..., х„): (Я+)" -> Я+ 0 (в) каторги определяется следующим образом.
Применим машину М к коду набора (аь аг,..., а„). Если М остановится и после остановки на ленте будет только код некоторого числа Ь Е Е+, то Давая,...,о ) = 6. Во всех остальных случаях Демаг,...,о ) = в (неопределенность). Определение. функция Дхьхг,...,х„): (Яч)" + о 0 (в) на.- зывается вычислимоб, если существует машина Тьюринга М, которая ее вычисляет. Определение. Говорят, что машина М правильно вычисляет функцщо ~(хьхг,...,х„), если, начиная работу с кода набора (аь..., а„), машина М в том случае, когда Даь аг,..., а„) не определено, обязательно работает бесконечно долго, а в том случае, когда у(ам аз,..., а„) = Ь, машина останавливается, на ленте остается код Ь и гопника маюивы обозревает самый левый символ ~.
Утвернсдеиие. Если Дхь хз,..., х„) вычислимо, тпо сутцесптвуеш машина Тьюринга М, котпорая ее вычисляет правильно. Доказательство см., например, в [18]. Определение. Всюду опрецеленные вычислимые функции мы будем называть общерекурсивными функпиями. (Обычно обшерекурсивные функции определяют иначе, но данное определение эквивалентно обычному; см., например, [18)). функция, вычисляемая машиной М, не изменится, если произвольно переименовать все символы ленточного алфавита, кроме [ и Л, н все состояния, оставляя начальное состояние начальным (конечно, разные символы должны переименовываться в разные). Поэтому мы будем считать, что есть бесконечный фиксированный алфавит (со = Л,ст =[,сз,сз,...), из которого берется ленточный алфавит машины М, и бесконечный фиксированный алфавит (оо, ум йз, .., 1, из которого берутся состояния машины М.
Будем записывать ннтюксы в строку после с нлн о, представляя их в двоичной системе счисления (например, св = с110). Программу машины М будем записывать в виде послаповательности всех ее команд с;у — + сьутТ, разделенных точкой с запятой. Тогда программа любой машины булет прелставлять собой слово в алфавите Р = (Л, ~, с, о, О, 1, — т, В, Е, 5,; ). Теорема 4.1. Сущесптвуетп алгоритпм нумерации всех машин Тьюринга иэ укаэанного выше семейства тапкой, чтпо оля восстпановленив программы по ее номеру тпакже сутцестпвуетп алгоритпм. Локаэапьельстпво.
Будем считать, что символы алфавита .Р упорядочены (например, так, как это сделано вылив). Тогда все слова одной длины к можно угюрядочить лексиграфически (как в словаре). Будем теперь просматривать все слова в алфавите Р в соответствии с их длиной: сначала длины 1, затем длины 2 н т.д. Слова одной длины к просматриваем в лекснкографическом порядке. Для каждого слова применяем алгоритм, который проверяет, является лн это слово правильно построенной программой некоторой детерминированной матлины Тьюринга. Если да, то приписываем этой программе очередной номер (начвнвя с О). При этом любой машине Тьюринга (из рассматриваемого семейства) по ее программе будет (алгорнтмвчно) сопоставляться некоторый номер.
Тот же перебор осуществляем, если задан номер и требуется найти соответствующую этому номеру программу. Зафиксируем далее некоторую нумерацию машин Тьюринга т ь — + М„удовлетворяющую теореме. Так как машина М, вычисляет некоторуто функцию 1(х), то мы получаем также некоторую нумера- цию всех вычислимых функпий одной переменной г — ь уг(х). Заметим, что при этом может быть р,(х) ы багз(х) при г ф у, поскольку разные машины Тьюринга могут вычислять одну и ту же функцию г (х). .Покажем теперь теоремы о том, что существуют сколь угодно сложно вычислимые функции. Теорема 4.2. Для любой общерекурсивной функции Т(х) существуета общерекурсивная функция Дх), принимаюигал только з значения О и 1 и такая, что для любой машины Тьюринва М„вычисллюгаей Дх), хонга бы при одном х выполняется неравенство гг(х) ) Т(х), еде й(х) — время работы магииньг М, на входе х (точнее, на коде числа х).
Замечание. Отметим, что функция Т(х) может расти очень быстро. Например, функции дг(п) = и, дз(п) = и", дз(п) = п™г, ..., д,„+г(п) = пв"<ьг, ... общерекурсивны. Также общереггурсивна и функция Ь(п) = д„(п), которая растет с астрономической скоростью. Яоказательство. Пля всех г. б Я" и х б Я+ пусть Ц(х) обозначает время работы машины с номером г, если входом является код числа х (гг(х) может быть и бесконечным), и пустыр,(х) обозначает фувкдию, вычисляемую машиной Мь Определим функцию ((х) следующем образом: ) 1, если г,(х) < Т(х) и ~р,(х) = О, '1 О, иначе.
Утверждение. Функиие Дх) — вычислимая, а с.гедовательно, общерекурсивнае. лгоказательство. Опишем алгоритм вычисления у(х). По заданному х б Я+ находим программу машины М, (см. теорему 4.1) . Вычисляем Т(х) (так как Т(х) — общерекурсивна, то для этого существует алгоритм). Имея программу машины М„моделируем ее работу в течение Т(х) тактов, взяв в качестве входного слова код числа х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
