Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 120

Можно воспользоваться таблицей на рис. 11.9. б) Укажите квадратичные вычеты по модулю 13. в) (!) Докажите, что если р является простым, то число квадратичных вычетов по модулю р равно (р — 1)~2, т.е. половина положительных целых чисел по модулю р — квадратичные вычеты. Указание. Проверьте ваши данные, полученные в частях а и б. Видите ли вы образец, позволяющий понять, почему каждый квадратичный вычет является квадратом одновременно двух разных чисел? Может ли одно целое число быть квадратом трех разных чисел, если р простое? Резюме + Класс со-ЛР. Язык принадлежрт со-ЛР, если его дополнение находится в ЛР.

Все языки из Р, очевидно, принадлежат со-Л'Р, но похоже, что сушествуют языки, принадлежащие ЛР, но не со-ЛР, и наоборот. В частности, ХР-полные проблемы, скорее всего, не принадлежат со-Л)э. + Класс Ро. Язык принадлежит Р8 (полиномиальное пространство), если он допус- кается детерминированной МТ, для которой существует такой полипом р(н), при котором на входе длиной и МТ никогда не использует более р(н) клеток ленты.

+ Класс ЛР5. Можно определить допускание недетерминированной МТ, использование ленты которой ограничено полиномиальной функцией от длины входа. Класс таких языков обозначается ЛРо. Однако теорема Сэвича гласит, что РЗ = ЛРо. В частности, НМТ с ограничением пространства р(н) может быть проимитирована с помощью ДМТ, используюшей пространство р~(н). + Рандомизированные шзгоритчы и млиины Твюриига. Многие алгоритмы продуктивно используют рандомизацию. В настоящем компьютере генератор случайных чисел используется для имитации "бросания монеты". Рандомизированная машина Тьюринга может достичь такого же случайного поведения, если ее снабдить дополнительной лентой, на которую записывается последовательность случайных битов. + Класс РР.

Язык допускается за случайное полиномиальное время, если существу- ет полиномиальная рандомизированная машина Тьюринга, имеюшая не менее 50;4 шансов на допускание своего входа, при условии, что этот вход принадлежит языку. Если вход не принадлежит языку, то зта МТ не допускает. Такая МТ нли алгоритм называются "типа Монте-Карло". 520 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ + Класс БРР.

Язык принадлежит классу безошибочного вероятностного полиномиального времени, если допускается рандомизированной МТ, которая всегда дает правильный ответ о принадлежности входа языку. Ожидаемое время работы этой МТ полиномиально, хотя в наихудшем случае может быть больше любого поли- нома. Такая МТ или алгоритм называются "типа Лас-Вегас". + Соотношения между классами языков. Класс со-ЯР— это множество дополнений языков из РР. Известны следующие включения: 'Р с ЗРР с; [РРП со-РР).

Кроме того, Т'Р ~ ]ч'Р и, следовательно, со-РР ~ со-ЛT. + Простые числа и зчР. Как язык простых чисел, так и его дополнение — язык составных чисел — принадлежат ЛlР. Эти два факта делают невероятной ХР-полноту данных двух языков. Поскольку на простых числах основаны важные системы шифрования, доказательство последнего утверждения служило бы строгим обоснованием их безопасности. е Простые числа и РР. Язык составных чисел принадлежит ЯР. Рандомизирован- ный полиномиальный алгоритм проверки, является ли число составным, обязан в общем случае допускать генерацию больших простых чисел нли, по крайней мере, чисел, имеющих сколь угодно малую вероятность быть составными.

Литература Изучение классов языков, определяемых с помощью ограничения пространства, используемого машинами Тьюринга, началось в [2). Первые РБ-полные проблемы описаны Карпом в статье [4], исследовавшей значимость [ЧР-полноты. Оттуда же РБ-полнота проблемы, представленной в упражнении 11.3.2, — является ли регулярное выражение эквивалентным Х . РБ-полнота булевых формул с кванторами доказана в неопубликованной работе Л. Стокмейера, а переключательной игры Шеннона [см. упражнение 11.3.3) — в статье [1].

Принадлежность языка простых чисел классу МР установлена Праттом в [9), а составных классу ЕР— Рабином в [10]. Интересно, что приблизительно тогда же в [6] было опубликовано доказательство, что множество простых чисел на самом деле принадлежит Р при условии, что верна так называемая расширенная гипотеза Римана [тогда в ее истинность многие верили). Вопросы данной главы подробнее освещены в нескольких книгах. Рандомизированные алгоритмы, а также полные алгоритмы проверки простоты представлены в [7].

Источником алгоритмов модулярной арифметики послужила [5]. В [3] и (8) изучены многие классы сложности, не упоминаемые здесь. 521 ЛИТЕРАТУРА Предметно-именной указатель НТМ1.. 207; 211 Нп!Тшап О. А., 98; 184 1пгегпег, 85 Л 1ойпзоп О. Я., 478 К Катр К. М., 479; 522 Кегп!8Ьап В. %., 320 К1еепе Б. С., 142; 184; 376 Кпп!Ь О. Е., 267; 522 Кпгзка! 3г.

3, В., 426 К-клика, 473 К-коньюнкгивная нормальная форма, 446 Е 1.ешь И Р. М., 522 Еех, 128 м Мсбапйу !., 99 МсСнйосЬ %. К, 98 МсНапййзоп К., 142; 184 Меа1уб. Н., 98 МП!ег б.! ., 522 М1пз!гу М. 1... 376; 421 Мооге Е. Г., 99; 184 Мопчап! К., 522 Ь1авг Р., 231 о Ое!Ппйег А.

б., 267 Ойг!еп %., 317 Р Рарай1ш!гг!оп С. Н., 522 Ранй М. С., 317 Рег!ез М., 184; 317; 421 Р!Пз%., 98 Роз! Е., 376; 42! Ргап Ч. К., 522 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ е-замыкание состояния, 91 е-НКЛ, 89; 91 е-переход, 89 А Аб!ешап 1... 510; 522 ЛЬо, А. Н., 52; ! 42; 23 1 в Вас!газ Ь 'чч'., 231 Ваг-НП1е! г., 184; 317; 421 ВогозЬ 1., 478 с Сап!ог О.

С., 231; 421 СЬошзйу !ч., 231; 317; 421 СЬпгсЬ А., 376 Соййып Л., 478 Соей К С., 478 Р ОТО, 207; 214 Е Ечеп К, 522 Ечеу 1„266 в Г!зсйег Р. С., 267; 376 Нех, 128 Г1оуг! К. %., 231; 421 С багеу М. К.. 478 байгеп 1„478 б!пзйпг8 Я., 184; 317; 421 бВЬег !. 1., 142 боебе1 К., 376 бге1Ьасй, Я., 3!7 СгКЕР, 128 бгозз М., 23! н Нштшвп!з 3., 184; 376; 479: 522 НосЬЬашп О. К, 479 Норсгой !. Е., 184; 522 К КаЬгп М. О., 99; 522 Каййачап Р., 522 К!се Н.

б., 398; 421 К1гсЫе О. М., 320 йбчезГ К. 1, 510; 522 Козе б. Г.,!84; 317; 421 КпгйсЬ Б., 376 Я Зачгсй %. !., 522 Ясйе1пЬег8 К, 317 ЗсйнгхепЬегйег М. Р., 267; 421 Зсон Г)., 99 Зе1регаз 3. 1,, 184 ЯеГЫ К., 142; 231 ЯЬапнг А., 510; 522 Гйаппг Е., 184; 317; 42! ВЬаппоп С. Е., 99 8! ечекйп8 М., 478 гй1з сггяеш С., 16 Крап!ег Е. Н., 184 гйеапзз К. Е., 184; 376; 479; 522 т Тат!во К. Е., 522 ТЬошрзоп К., 142 ТгеуЬгй 1..

В., 478 Твпп8А. М., 376; 421 Ю Бйшап й О., 52; ! 42; 231; 479; 522 13!Ч!Х, 126; 131; 210 ХМ1., 207; 214 "г'ЛСС, 210; 223 г'шпаг!а Н., 142 Уовпйег О. Н., 317 А Автомат конечный, 17; 53 детерминированный, 62 минимальный, 177 623 в г Гедель К., 329 Генератор недетерминнрованный, 71; 73 магазинный, 234; 235 детерминированнный, 260 ограниченный, 251 недетерминированный с е-переходами, 89; 91 -произведение, 59 Адрес слова памяти, 367 Алгоритм заполнения таблицы, 173 Кока-йнгера-Касами, 311 Крускача, 426 минимизации ДКА, 179 типа Лас-Вегас, 507 типа Монте-Карло, 504 Алфавит, 46 бинарный,46 двоичный, 46 Анализатор лексический, 18 Аннулятор, 113; 134 Арифметика модулярная, 5! 2 Ассоциативность, !33 Ахо А., 52; 142 Базис индукции, 36 Блок состояний„!78 Булеан множества, 77 Временная сложносгь машины Тьюринга, 350 Время работы машины Тьюринга, 349 Вхождение свободное,492 связанное, 492 Выведение, 189 Вывод рекурсивный, 189 Выражение арифметическое, 41„ !87; 224 булево,436 регулярное.

20, !01; 104 конкретное, 137 расширенное в 1714! Х, 126 Высота дерева, 202 Вычет квадратичный, 520 Вычисление. 240 лексических анализаторов, 102 лексического анализатора, 128 Гильберт Д., 329 Гипотеза, 22 Черча, 330 Гишер Дж., 142 1 олова продукции, 187 Головка, 330 Гомоморфизм обратный, 157; 302 цепочек, 156 языка, 156 Грамматика, 20; 187 контекстно-свободная, 187 праволинейная, 196 формальная, 17 Хомского, 17 Граф, 425 График функции, 339 Грейбах Ш., 284 Дерево, 198 корневое, 40 остовное, 425 минимального веса, 425 разбора, 197 Дескриптор, 207; 21! Дишрамма переходов.

64 машины Тьюринга, 334 МП-автомата, 237 Дизъюнкт, 446 ДКА, 62 ДМП-автомат, 260 Доказательство дедуктивное, 22 индуктивное,22 методом "от противного", 34 Дополнение языка, 149 Достаточность, 28 Единица, 47; 134 Задача 14р-трудная, 17 линейного цеяочисленного программирования, 475 трудно разрешимая, 17 труднорешаемая, 17 Заключение, 22 Закон ассоциативности конкатенации, 133 обьединения, 133 умножения, 133 двойного отрицания, 448 Де Моргана, 152; 448 дистрибутивности, 134 конкатенации относительно объединения левосторонний,135 правосторонний,!35 объединения относительно пересечения, 3! умножения относительно сложения, 134 идемпотентности, 135 объединения, 136 коммутативности объединения, 133 сложения, 133 коммутатнвный обьединения множеств, 31 Мура, 17 Замыкание Клини, 103 Значение формулы, 437 Игра "катящиеся шарики*', 69 Идентификатор, 187 Индексы обращенные, 85 Индуктивный переход, 36 шаг, 36 Индукция, 36 совместная, 43 структурная, 40; 42 Исключение сосгояний, 115 Итерация языка, 103 Карп Р., 434 Квантификация, 491 Кваитор, 27 Керниган Б, 320 Класс символов, ! 26 языков РсР, 504 ЗРР, 506 Класс проблем Со-ЛГР, 482 Лгр, 424; 429 Л7Ю, 485 024 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Р, 424 РБ, 485 Класс языков АгРо, 485 РБ, 485 Клини С., 103; 142 Ключ публичный, 511 Кнут Д., 15 КНФ, 446 Код машины Тьюринга, 379 Коммугативность, 133 Компилятор, 18 Компонент связности, 426 Конверсия, 33 Конечное управление, 330 Конкатенация, 47 языков, 102 Конструкция подмножеств, 77 произведения, !52 Контрапозиция,32 Контрпример, 34 Конфигурация, 238 машины Тьюринга, 33! Конъюнктивная нормальная форма,446 Конъюнкция, 43 Корень дерева, 40 Кронадерева, !99 КС-грамматика, 187 неоднозначная, 221 однозначная,222 КС-язык, 193 существенно неоднозначный, 226 Кук С., 434; 439 Лампорт Л., 15 Левин Л.

А., 479 Лексема, 102; 128 Лексический анализатор, 128 Лемма о накачке для КС-языков„288 для регулярных языков, 144 Огдена, 294 Лента машины Тьюринга, 330 односторонняя,356 случайная, 500 Леск М., 142 Лист дерева, 198 Литерал, 446 Магазин, 233 Мак-Каллок У„98 Мак-Карти Дж., 99 Мак-Нотон Р., 142 Маркер дна, 360 концевой, 360 Машина многомагазиннач, 359 мультистековая, 359 счетчиковая, 361 Тьюринга, 17; 330; 331 двухмерная, 355 многогаловочнгл, 355 многоленточная, 347 недсгерминированная, 351 рандомизированная, 500 типа Лас-Вегас, 507 типа Монте-Карло, 504 универсальная, 337 Мгновенное описание, 238; 331 Метод обращенных индексов, 85 Мили Дж., 98 Минимизация ДКА, 177 Множество, 25 бесконечное, 25; 28 дополнение, 25 ключевых слов, 37 конечное, 25 независимое„453 максимальное, 458 несчетное, 322 счетное, 322 Монус, 335 МП-автомат, 234; 235 Мур Э., 99 Наблюдение, 34 Необходимость, 28 Нетермииаз, 187 НКА, 71 Нормальная форма Грейбах, 284 Хамского, 269; 230 Нуль, 134 НФХ-грамматика, 280 Область действия переменной, 491 Обращение цепочки, !54 языка, 154 Объединение языков, 102; 149 Огден У., 294 Оператор ?,!27 (и), 128 !.