М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 47
Текст из файла (страница 47)
Например, многоленточные машины Тьюринга могут решать многие задачи существенно быстрее, чем одноленточные. Эта трудность разрешается довольно грубым способом. Предположим, что на вход подается и битов (например, нам может быть нужно узнать, является ли простым данное и-битовое число). Главное различие, кзторое проводится в теории сложности, — это различие между задачами, которые можно решить с использованием ресурсов, объем которых ограничен сверху многвчленвм отп и, и задачами, для которых необходимый объем ре- 186 Глава 3. Введение в информатику сурсов растет быстрее, чем любой многочлен от и.
В последнем случае обычно говорят, что задача требует экспоненциальнмх ресурсов (злоупотребляя словом «экспоненциальный»: существуют функции, например имг", которые растут быстрее любого полинома и тем самым являются «экспоненциэльными» в нашем смысле, но при этом растут медленнее любой настоящей экспоненты). Задача считается легкоа, простой или решаемой, если для ее решения существует полииомиальный алгоритм, и гпрдоной, сложной или нерешаемой если наилучший возможный алгоритм требует экспоненциального объема ресурсов.
В качестве простого примера рассмотрим два числа с двоичными записями х1... х, и у1... у~, и предположим, что нужно найти их сумму. Общий объем входных данных равен и = п»1 + гпг. Легко видеть, что числа можно сложить, используя 9(т) элементарных операций; этот алгоритм использует полиномиальное (а именно, линейное) число операций. Напротив, считается (хотя это так и не доказано!), что задача разложения числа на простые множители является сложной и, что не существует алгоритма, с помощью которого произвольное п-битовое число можно разложить на простые множители с помощью 0(р(и)) операций, где р — некоторый фиксированный многочлен от и.
Ниже мы приведем много других примеров задач, считающихся сложными в этом смысле. Разделение задач на полиномиальные и экспоненциальные является довольно грубой классификацией. На практике алгоритм, решающий задачу за 2"7шоо операций, является, возможно, более полезным, чем тот, который использует и1ооо операций. Только при очень большом (п ю 10 ) объеме входных данных этот «эффективный» полиномиальный алгоритм будет предпочтительнее «неэффективного» экспоненциального и для многих целей разумнее будет пользоваться именно «неэффективным» алгоритмом.
Однако существует много причин, по которым имеет смысл основывать теорию сложности вычислений именно на разделении алгоритмов на полиномиапьные и экспоненциэльные. Во-первых, исторически за малым числом исключений сложилось так, что полиномиальные алгоритмы работали существенно быстрее экспоненциальных. Можно по,пумать, что причина этого в недостатке нашего воображения: разработать алгоритм, в котором число операций равно и, и~ или какому-нибудь еще многочлену маленькой степени, часто гораздо проще, чем алгоритм, требующий п'~~ операций, хотя и такие примеры существуют. Так что склонность человека к построению относительно простых алгоритмов привела к тому, что на практике полиномиальные алгоритмы работают достаточно эффективно.
Вторая и более серьезная причина того, что имеет смысл настаивать на разделении алгоритмов иа полиномиальные и экспоненциальные, связана с сильной формой тезиса Черча-Тьюринга. В рэзд. 1.1 мы уже обсуждали, что в 60-70-х гг. было замечено, что вероятностная машина Тьюринга является сильнейшей из «разумных» вычислительных моделей. Точнее говоря, различные исследователи независимо пришли к выводу, гго если можно вычислить функцию с помощью Й операций на некоторой модели, не являющейся вероятностной машиной Тьюринга, то на вероятностной машине Тьюринга ту же 3.2.
Анализ вычислительных задач 187 самую функцию можно вычислить не более чем за р(Й) операций, где р( )— некоторый многочлен. Это утверждение известно как усиленный тезис Черчуьюринга: Тезис Черча — Тьюринга (усиленная форма). Любая вмчислитлвльная модель молсет быть смодглирована на вероятностной маигинв Тьюринга с не более чем палинамиальнмм увеличением числа оаераций. Усиленный тезис Черча-Тьюринга имеет большое значение для теории сложности вычислений в том отношении, что из него вытекает, что все внимание можно сосредоточить на вероятностной машине Тьюринга.
Если задача не допускает полиномиального решения на вероятностной машине Тьюринга, то из этого тезиса следует, что нн на каком вычислительном устройстве она не имеет эффективного решения. Теория сложности вычислений принимает элегантный ввд и перестает зависеть от выбора модели, если только отождествить эффективность алгоритма с его полиномиэльностью, и именно эта элегантность подтолкнула исследователей на отождествление понятий «разрешимость с полвномиальными ресурсами» и «эффективная разрешимость». Конечно, одна из основных причин, по которым квантовые компьютеры представляют интерес, это то, что они подвергают усиленный тезис Черча-Тьюринга сомнению, так кэк позволяют эффективно решить задачи, которые считаются сложными для всех классических компъютеров, включая вероятностные машины Тьюринга! Тем не менее полезно понять и оценить ту роль, которую усиленный тезис Черча-Тьюринга сыграл в процессе построения не зависящей от модели теории сложности вычислений, Отметим в заключение, что специалисты по информатике интересуются не только разделением задач на полиномнальные и экспоненциальные.
Это лишь первый и самый грубый способ оценки трудности вычислительных задач. Тем не менее такое разделение является исключительно важным; оно иллюстрирует многие более общие вопросы, связанные с проблемой потребления ресурсов при вычислениях. В большей части этой книги при оценке эффективности алгоритма мы будем в первую очередь руководствоваться именно отличием полиномиальности от экспоненциэльности. Теперь, когда мы обьяснили, чем хорошо разделение алгоритмов на полиномигльные и экспоненциальные, еле,зует признаться, что у теории сложности вычислений имеется один крупный недостаток: по-видимому, очень трудно доказать, что существуют интересные классы задач, для котОрых нет полиномивльных алгоритмов. Совсем легко дать неконструктивное доказательство того факта, что для большинства задач требуются экспоненциэльные ресурсы (см.
упр. 3.16), и более того, существуют гипотезы, согласно которым для многих задач требуются экспоненциальные ресурсы, но строгих доказательств этих гипотез нет и представляется, что найти эти доказательства очень трудно, по крайней мере, при современном состоянии предмета. Этот недостаток теории сложности вычислений имеет важные последствия и для квантовых вычисленнй, поскольку эффективность квантовых компъютеров сравнивается с эффек- 188 Глава 3.
Введение в информатику тивностью классических вычислительных моделей. До тех пор, пока основные проблемы классической теории сложности вычислений не будут решены, об эффективности квантовых компъютеров нельзя сказать ничего определенного; нельзя даже сказать, действительно ли квантовый компьютер эффективнее классического компьютера. Упражнение 3.16 (экспоненциально вычислимые функции существуют). Покажите, что существуют булевы функции с и аргументами, для вычисления которых требуется не менее 2" / 1о8 и логических элементов.
3.2.3 Задачи разрешения и классы сложности Р и ХР Многие вычислительные задачи лучше всего формулируются как задачи разрешения, т. е. задачи, дающие ответ в виде «да» или «нетм Пример: является данное число гп простым или нет? (это задача определения простатам). Основными для теории сложности вычислений являются именно задачи разрешения по двум причинам: во-первых, при этом теория принимает наиболее простой и элегантный вид, но при этом остается возможность ее естественного обобщения на более сложные случаи и, во-вторых, исторически теория сложности вычислений возникла прежде всего из анализа задач разрешения.
Хотя большинство задач разрешения легко сформулировать на простом и знакомом языке, обсуждение общих задач разрешения сильно облегчается, если воспользоваться понятием формального лзмка. Язытм Ь в алфавите Е называется подмножество множества Е', состоящего из всех конечных строк символов алфавита. Если, например,,Е = (О, Ц, то множество двоичных записей четных чисел Ь = (О, 10, 100, 110,...) является языком в алфавите Е. Задачи разрешения можно очевидным образом переформулировать как задачи о языках. Например, задача определения простоты может быть сформулирована с помощью двоичною алфавита Е = (О, Ц. Строки из Е' можно интерпретировать как целые неотрицательные числа (например, 0010 — это число 2).
Язык А определим как состоящий из двоичных строк, соответствующих простым числам. Чтобы решить задачу определения простоты, нам нужна машина Тьюринга, которая, при подаче числа и на вход выдает какой-то эквивалент ответа «да», если число простое, и выдает «нет», если число составное. Для того, чтобы уточнить это определение, нам будет удобно слегка модифицировать наше прежнее определение машины Тьюринга (подразд. 3.1.1), заменив заключительное состояние оь на пару состояний ву и оп, представляющих ответы «да» и «нет» соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
