В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 17

Задача о квавтифицированных булевских формулах (С)ВЕ). Вход: формула вида ж *)(а.*.)... (Е * )[Р(*..",* )], тле хм... >х,„— булевские переменяые, Р— булевская формула в базисе 1>конъюнкция, двзъюнкция, отрицание~, >Ъ б (3, Ч~ дпя всех т. 2'ребус>поят выяснить, истинна ли данная формула. Лемма 6.2. ЯВР б РБРАСЕ. Доназатпе встпва. Пусть на вход поступила формула Я~хт)(>>в>зхэ)... (Я>нх>„)[Г(хц...,х )], длины и.

Тогда длина формулы Р(хц..., х ) не более п, и для любого задаввогонэбора(а>,...,а ) вычкслевиеР(тэм...,а ) можновьшол- вить за время, а значит и с использованием памяти, не более р> (и), где рт — некоторый полипом. Если зафиксированы только значения ап...,>зэ переменных хь, ..,хм то мы получаем подзадачу: найти истивностное значение формулы (>ттьт>хаы) ° ° ° Ж»>х>н)[Р(т"1> >зт» хь+ь ' > х»>)]' Применим для решения исходной задачи (и всех ее подзадач) следую- щий рекурсивный алгоритм: 1. Вычислять Яэхэ)...

(Я„,х„,)Р(0>хэ,...,х,„) этим же рекур- сввиым алгоритмом. Запомнить полученное значение (1 бит) в допол- виз633з>нОЙ ячейке. тт 2. Вычислить на той же зоне этим же алгоритмом (азиз)... (ьчЬьохоь)Р(1ь язв .. ь хоь) 3. Если Яь — — Ч и оба значения, вычисленные в 1 и 2, равны 1, то выдать ответ 1, иначе выдать О. Если (~ь = 3 и оба значения в 1 и 2 равны О, то выдать О, вначе выдать 1. Из описания алгоритма видно, что для решения задачи каждого уровня нужно на 1 ячейку больше, чем на решение любой ее подзадачи.

Тах как на вычисление Р(аь,.,., а„,) требуется дамлти не более рь(п), то для вычисления истинностного значения исходной формулы требуется память не более рь(п) + п ячеек. Для управления пронессом перехода от одних подзадач к другим в описанном алгоритме достаточно помнить, какал подзадача решаетсл в данный момент, то есть помнить значения аь,..., аы опрецеляюшие эту подзадачу. Таким образом, в целом оприсанный алгоритм требует не более р(п) ячеек памяти, где р — некоторый поливом.

Теорема 6.2. Задача ь тВР лелястпсл РБРАСЕ-по ьпой. Яопазаиьельстпво. Нам надо доказать, что любак задача Ь из РБРАСЕ полиномиально сводится к ЯВУ. Если В Е РБРАСЕ, то супьествует машина Тьюринга М, которэл решает задачу В с памятью не более рь(п) и временем не более 2"ь"ь (см. лемму 6.1), где п — длина вхцца. Пусть з — вход длины п для задачи Ь. Нам надо за полнномиальное время построить квантнфицировавную формулу Рйй так, что Гь 1 истинна тогда и тольхо тогда, когда з Е Ь. Тот факт, что х Е Ь, равносилен утверждению: для входа х существует цринимаюшее (с ответом "да") вычисление маппшы М. Это последнее утверждение мы и выразим в виде формулы Рь*ь. Так же, как при доказательстве гт Р-полноты задачи ВЬП1, введем два множества переменных ьт и 7т, описывающих 2 произвольные конфигурации на зоне рь(ть); и запишем формулу Ро(ьт, Ъ"), выражающую 'тот факт, что р' и рт правильно задают конфигурации и либо 1т = 1т', либо из конфигурации ьт мы за один шаг машины М переходим в конфигурацию ь'.

Как показано при доказательстве ььтР-полноты задачи ВЫП длина формулы Ро(ь;'ьт') может быть ограничена некоторым полиномом рз(п) и ее можно построить за полиномиальное от п время. Формула Ро(1т,'ти) выражает тот факт, что из конфигурации ьт в конфигурацию т'т можно перейти за не более чем 1 шаг. Построим теперь индуктввно формулы Рь, Рз,..., Р„где з = р(п), слецуюшвм образом. Пусть И~ — еще одно множество переменных, описывающих конфигурацию на зоне рт(п).

Тогда положим Р»(КУ') = ЗИ~[Р»»(У,И~)йР»»(И', У')]. Формула Р» выражает тот факт, что У, У' — правильные конфигурации и из У в У' можно перейти за не более, чем 2 шагов. Формула в квадратных скобках равносильна следующей формуле: (И')(ЧЕ) [(У = У)й(Я = И') ч (У = И')й(Я = У ) -э Р»»(У, Е)] гле У,2 — два множества переменных, описывающих 2 произвольные конфигурации на зоне р»(и). Поэтому формулу Р» можно записать в виде: Р»(У, У') = (ВИ ) (~У)(~~) [((У = У)й(ь = И') Ч (У = И~)й(Я = Ъ")) -» Р»»(У, 2)]. Таким' образом, длина Р»(Ъ', У') отличается от длины Р» 1(У, У') не более чем на некоторый поливом рз(п) и дивна Р»(К У') не превосходит рз(п) + йрз(п).

Пусть время работы мал»ивы М не превосходит 27~"1 и з = р(п), Тогда Р,(Ъ', У') имеет длину не более рз(п) + р(п) рз(п) = р»(и), гле р4 — полипом, и выражает тот факт, что У и У' правильные конфигурации и из И в Ъ" можно перейти за не более 29~"~ шагов машины М. Пусть формула 0 (У) выражает тот факт, что конфигурация У является правильной начальной конфигурацией для входа х (на зоне р1(п)), а фррмула Н(У) выражает тот факт, что в конфигурации У состояние "ла". Тогда тот факт, что для входа х существует принимающее вычисление машины М можно представить формулой Р" =( )(~У)[С.(У)йН(У') .(У,У')] Поскольку длина формул С,(У) и Н(У) может быть ограничена лолиномом от п и они могут быть построены за полиномиальное от п время (см.

доказательство НР-полноты задачи ВЫП), то получаем, что длина Р~*~ не превосходит полвнома от и и Р~*~ может быть построена за полиномиальное от п время. Теорема доказана. При определении класса 1ЫОС обычно используют модель многоленточной машины Тьюринга. Пусть у машины Тьюринга имеется несколько лент, одна из которых выделена как входная, и на каждой ленте имеется одна головка. Один шаг работы такой машины состоит в одновременном выполнении обычных действий каждой головкой (у каждой головки свои действия), причем весь набор действий однозначно определяется теми символами, хоторые обозреваются всеми голов- хами и состоянием машины. Вхсдное слово записывается на входной 79 ленте в стандартной конфигурапии и головка на входной ленте может только читать символы, но не может записывать новые.

Определение. Класс РйОС определяется как класс всех задач распознавания (языков), для которых существует распознающая их многоленточная машина Тьюринга, использующая на всех лентах, кроме входной, не более с 1ояз п ячеек, где и — длина входа и с — некоторая константа (для данной задачи). Используя лемму 6.1, нетрудно показать, что РйОС С Р. Таким образом ВйОО С Р С ИР С РБРАСЕ. Можно доказать, что РАМОС ф РБРАСЕ, позтому хотя бы одно из указанных включений должно быть строгим, Однако какое (или какие) именно, пока (2002 год) не известно. Литература 1. Алексеев В.

Б. Логические полукольца и их использование для построения быстрых глгортмов // Вестник ЮГУ, Серия 1. Матпематика, механика — 1997, Н 1. — С. 22-29. 2. Алексеев В. Б. Сложность умножения матрип (обзор) // В кн. Кибернетпическиб сборник, новая серия, вьш. 25 — Мл Мир, 1988. С.

189-236. 3. Алексеев В. Б., Ложкин С. А. Элеменнты тпеории графов, схем и автпоматов — Мл Издательский отдел ф-та ВМиК МГУ, 2000.— 58с. 4. Ахо А., Хопкрофт Дж., Улыбин Дж. Постпроение и анализ вычислительных алгоритмов. — Мл Мир, 1979. — 536 с. 5. Барздинь Я. М. Сложность распознавания симметрии на машинах Тьюринга // В сб. Проблемы кибернетпики, вып.

15 — Мл Наука, 1965. С. 245-248. 6. Вороненка А. А. О сложности распознавания монотонности // В кн. Математические вопросы кибернетпики, вып. 8 — М.: Наука-физматлит, 1999. С. 301-303. 7. Гэри М., Джонсон Д. Вычислитпельные машины и трудноретааеные задачи. — Мл Мир, 1982. — 416 с.

8. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ПАП СССР— 1962. — Т. 145. — Н 2. — С. 293-294. 9. Кнут Д. Э. Искусство программировании. Т. 8. Получисленные алгоритпмы. — 3-е изд. — Мл "Вильямс", 2000. — 832 с. 10. Кнут Д. Э. Искусстпво программирования. Т. У. Сортировка и поиск. — 2-е изл. — М.; "Вильямс", 2000. — 832 с. 11. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорито автпоматов.

— Мл Наука, 1985. — 320 с. 12. Кук С. А. Сложность процедур вывода теорем // В кн. Кибернетический сборник, новая серия, вьш. 12 — Мл Мир, 1975. С. 5-15. 13. Папгдкмитриу Х., Стайглзш К. Комбинатпорная оптпимизаиия. Алгоритмы и сложность. — Мл Мир, 1985. — 510 с. вт 14. Рейнгольд Э., Нивергельт Ю., Лео Н. Комби»атор»ые алгоритмы. Теория и практика. — М.:Мир, 1980. — 476 с. 15. Тоом А. Л. 0 сложности схемы из функциональных злемевтов, реализующей умножение целых чисел // НАН СССР— 1963.— Т.

150. — С, 496-498. 16. Шенхаге А., Штрассен В. Быстрое умножение балыках чисел // В кн. Кибернетический сборник, новая серия, вьш. 10 — Мс Мир, 1973. С. 87-98. 17. Штрассен В. Алгоритм Гаусса не оптимален // В кн. Кибер»ети- ческий сбор»ик, новая серия, вып. 7 — Мс Мир, 1970. С. 67-70. 18.

Яблонский С. В. Введе»ие е дискрет»ую математику. — 3-е изд. — Мс Высшая школа, 2001. — 384 с. Учебное пособие АЛЕКСЕЕВ Валерий Борисович ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ АЛГОРИТМОВ Издательский отдел факультета ВМиК МГУ 1лицеизия ИД №05899 от 24.09.01) Напсчлгвно с готового оригинал-макета в нздвтельствс 000 "МАКС Пресс" Лнпслзил ИД 1Ч 00510 от О! 12 99 г.

Подписано к печвти 09.07.2002 г. Формвт бОх90 1П 6. Уел печ.л. 5 25. Тарик 150 зкз Заказ 58! . Тел. 939-3890, 939-3891, 928-1042. ТсвУФекс 939-3891. 119899, Москве, Воробьевы горы, МГУ. .