(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 4
Текст из файла (страница 4)
любой алгоритм, имеющий полиномиальнуювременную сложность при одной из этих схем кодирования,будеттакжеобладатьполиномиальнойвременнойсложностью при всех остальных схемах.Стандартные схемы кодирования, используемые напрактике для любой конкретной задачи, по-видимому, всегдабудут отличаться друг от друга не более чем полиномиальнымобразом. Трудно представить себе разумнуюсхемукодирования какой-либозадачи, которая отличалась быболее чем полиномиальным образом от стандартных схем.Хотя мы не можем формально выразить такое понятие, как«разумная схема кодирования», следующие два условияохватывают важные требования, связанные с этим понятием:(1) код любой индивидуальной задачи I не должен содержатьизбыточной информации или символов;(2) числа, входящие в условия задачи I, должны бытьпредставлены в двоичной системе счисления (или десятичной,или восьмеричной, или иметь любое другое основание, нотолько не 1).Если мы ограничимся рассмотрением тех схемкодирования, которые удовлетворяют (1) и (2), то выяснениевопроса, является ли данная задача трудно решаемой, не будетзависеть от выбора конкретной схемы кодирования.шв№ 8Ifame Тшцитс1я»Щ JНТ)ШТН^лщхщшмешена 4ШТш• *«ОШп)).(Ьтт Тьщтас ктщя(кПТ)0(?Чп})them ф&рйщтНищие0(ТЧп)), OiTHn))0(ТЬ)1щТ{п)}снтШмШ)Рис.
1.6 Время, требуемое машиной А длямоделирования работы алгоритма сложности Т(п) намашине В .Аналогичные замечания можно сделать относительновыбора модели ЭВМ. Все известные в настоящее времяреалистические модели ЭВМ (например, одноленточные имноголенточные машины Тьюринга и др.) эквивалентныотносительнополиномиальнойвременнойсложности.Вероятно, и любая иная «разумная» модель ЭВМ будетэквивалентна по сложности всем перечисленным моделям (см.рис. 1.6).Говоря «разумная модель» мы имеем в виду, что объемработы, выполняемой машиной в единицу времени, ограниченсверху полиномом. Например, модель со способностьювыполнять параллельно произвольно много операций, небудетсчитаться«разумной».Еслиограничитьсярассмотрением стандартных моделей реальных ЭВМ, то класструднорешаемых задач не будет зависеть от выбораконкретной модели.ЗАДАЧИ, ТРУДНОРЕШАЕМОСТЬ КОТОРЫХДОКАЗУЕМАПосле обсуждения формального содержания понятия«труднорешаемая задача», дадим краткий обзор наших знанийо существовании труднорешаемых задач.Имеется два аспекта труднорешаемости, которыеотражены в определении.
Первый аспект состоит в том, чтодля отыскания решения требуется экспоненциальное время.Второй заключается в том, что искомое решение настольковелико, что не может быть представлено в виде выражения,длина которого ограничена полиномом от длины входа.Вторая ситуация возникает, например, если в задаче окоммивояжере в качестве дополнительного параметрафигурирует число В и требуется найти все маршруты длины,не превосходящей В. Легко построить индивидуальную задачуо коммивояжере, в которой имеется экспоненциальное числомаршрутов длины, не превосходящей В, поэтому несуществует алгоритма с полиномиальной временнойсложностью, который все их перечисляет.Труднорешаемостью этого вида нельзя пренебрегать иочень важно ее обнаружить.
В большинстве случаев, однако,ее наличие видно из постановки задачи. Этот аспекттруднорешаемости рассматривается как указание на то, чтопостановка задачи не реалистична, посколькумызапрашиваем больше информации, чем сможем использовать.В связи с этим мы будем рассматривать только первый типтруднорешаемости. Будут изучаться только такие задачи,длина решения которых ограничена полиномиальнойфункцией от длины входа.Первыерезультатыо труднорешаемостизадач(классические результаты о неразрешимости) были полученыА.
Тьюрингом. Тьюринг доказал, что некоторые задачинеразрешимы в том смысле, что вообще не существуеталгоритма их решения. Он доказал, что невозможно указатьалгоритм, который по произвольной программе определял бы,остановится ли эта программа на произвольно заданном входеили нет. Неразрешимые задачи не могут быть решеныникаким алгоритмом и труднорешаемы в самом сильномсмысле.Первые примеры труднорешаемых разрешимых задачбыли получены в начале 60-х годов. Однако эти примерывключали только искусственные задачи, специальнопостроенные, чтобы обладать соответствующими свойствами.Только в начале 70-х годов удалось показать, что некоторыеестественные разрешимые задачи труднорешаемы.В число этих задач вошло большое число изучавшихсяранее задач из теории автоматов, формальной теории языков иматематической логики.
Было показано, что эти задачи немогут быть решены за полиномиальное время даже спомощью«недетерминированного»вычислительногоустройства, выполняющегопараллельно неограниченноеколичество независимых вычислений. В дальнейшем мыувидим, что эта модель вычислительного устройства играетважную роль в теории NP-полных задач.Всеизвестныевнастоящеевремязадачи,труднорешаемость которых доказана, попадают в один изклассов: они либо вовсе неразрешимы, либо труднорешаемынедетерминированноймашиной.Однако большинствопредставляющихся труднорешаемыми практических задач вдействительности разрешимы и, более того, могут бытьрешенызаполиномиальноевремяспомощьюнедетерминированноговычислительногоустройства.Известные методы недостаточно сильны, чтобы установитьтруднорешаемость этих задач.NP-ПОЛНЫЕ ЗАДАЧИПока продолжается поиск более мощных методовдоказательства труднорешаемости задач, параллельно ведутсяработы по сравнению сложности различных задач.
Как ужебыло сказано, обнаружение таких взаимосвязей междузадачами часто может дать разработчику алгоритмовполезную информацию.Основной метод, используемый для доказательства того,что две задачи близки, состоит в сведении их друг к другу спомощьюконструктивногопреобразования,котороеотображает любую индивидуальную задачу первого типа вэквивалентную ей индивидуальную задачу второго типа.Такое преобразование позволяет превратить любой алгоритмрешения второй задачи о соответствующий алгоритм решенияпервой задачи.Много примеров подобной сводимости известно ужедавно, Например, Эдмондс свел задачи из теории графов(найти минимальное вершинное покрытие графа и найтиминимальное независимое множество вершин графа) к задачео покрытии. Было дано описание хорошо известнойсводимости задачи о коммивояжере к задаче о кратчайшемпути, в которой допускаются ребра отрицательной длины.Эти первые сводимости хотя и были изолированы иотносились к узкому кругу задач, предвосхитили духрезультатов, которые доказываются в теории NP-полныхзадач.Фундамент теории NP-полных задач был заложен вработе С.
Кука, опубликованной в 1971 г. под названием«Сложность процедур вывода теорем». В этой короткой, ноэлегантной работе Кук получил несколько важныхрезультатов.Во-первых,онподчеркнулважностьпонятия«сводимость за полиномиальное время», т. е. сводимость,которая выполняется с помощью алгоритма с полиномиальнойвременной сложностью (если одна задача сводится заполиномиальное время к другой, то любой полиномиальныйалгоритм решения второй задачи может быть превращен вполиномиальный алгоритм решения первой).Во-вторых, он обратил внимание на класс задачраспознавания свойств (класс NP), которые могут бытьрешены за полиномиальное время на недетерминированномвычислительном устройстве (задачей распознавания свойствназывается задача, решениями которой могут быть ответылибо «да», либо «нет»).
Большинство не поддающихсярешению задач, которые встречаются на практике, послепереформулировки их в виде задач распознавания попадают вэтот класс.В-третьих, С. Кук доказал, что одна конкретная задача изNP, называемая задачей о выполнимости, обладает темсвойством, :что всякая другая задача из класса NP может бытьсведена к ней за полиномиальное время (такие задачиназываются универсальными).
Если задача о выполнимостиможет быть решена за полиномиальное время, то и любаязадача из класса NP полиномиально разрешима, а если какаято задача из NP труднорешаема, то и задача о выполнимоститакже должна быть труднорешаемой. Таким образом задача овыполнимости - самая трудная в классе NP.Наконец, С. Кук предположил, что и другие задачи изкласса NP могут быть, как и задача о выполнимости, самымитрудными представителями класса NP. Он показал это дляследующей задачи «содержит ли заданный граф G полныйподграф с заданным числом вершин?»Вслед за этим был доказано, что многие хорошоизвестные комбинаторные задачи, включая задачу окоммивояжере,сформулированныеввидезадачираспознавания, столь же трудны, как задача о выполнимости.Касс эквивалентности, состоящий из самых трудных задач изNP, получил название «класс NP-полных задач» (т.н.универсальный класс).Оригинальные идеи Кука позволили свести многоразнообразных вопросов о сложности в единый вопрос:«Верно ли, что NP-полные задачи труднорешаемы?» Внастоящем пособии приводится много различных задач, NPполнота которых уже установлена.Вопрос о труднорешаемости считается одним изосновных открытых вопросов современной математики итеоретической кибернетики.
Вопреки предположению, что всеNP-полные задачи труднорешаемы, прогресс как вдоказательстве, так и в опровержении этого далеко идущегопредположения весьма незначителен. Несмотря на отсутствиедоказательстватого,чтоизNP-полнотыследуеттруднорешаемость, NP-полнота задачи означает, что для еерешения полиномиальным алгоритмом требуется, по крайнеймере, крупное открытие.ТЕОРИЯ NP-ПОЛНЫХ ЗАДАЧМы изложим формальный аппарат теории NP-полныхзадач. Чтобы эта теория приобрела строгие математическиечерты, необходимо дать формальные эквивалентны многихинтуитивных понятий, например таких, как «задача» и«алгоритм». Основная цель состоит в выявлении связи междуформальными терминами и интуитивными понятиями,которые чаще всего используются.
Овладев этой связью, мысможем далее вести изложение главным образом нанеформальном уровне, обращаясь к формальному толькотогда, когда это необходимо.Начнём с обсуждения задач распознавания свойств ипредставления этих задач в виде языков, что даст возможностьотождествитьрешениезадачи сраспознаваниемсоответствующего языка. Основной моделью процессавычисления будет одноленточная машина Тьюринга, котораяиспользуется для определения класса Р (Polynomial —полиномиальный)всехязыков,детерминированнораспознаваемых за полиномиальное время. Машина Тьюрингазатемдополняетсягипотетическойспособностью«угадывания», и эта дополненная модель используется дляопределения класса NP всех языков, «недетерминировано»распознаваемыхзаполиномиальноевремя(NondetenninislicallyPolynomial).Послеобсуждениявзаимосвязи классов Ри NP определяется понятиеполиномиального преобразования одного языка в другой. Этопонятие применяется для определения наиболее важногокласса — класса NP-полных задач.
Завершим мыформулировкой и доказательством фундаментальной теоремыКука, которая даст нам первую NP-полную задачу.ЗАДАЧИ РАСПОЗНАВАНИЯ, ЯЗЫКИ ИКОДИРОВАНИЕТеория NP-полных задач строится только для задачраспознавания свойств. Такие задачи имеют только двавозможных решения - «да» или «нет». Задача распознаванияП состоит из двух множеств: множества Dn всех возможныхиндивидуальныхзадачимножестваYn(Ync D n)индивидуальных задач с ответом «да». Содержательныезадачи распознавания, как правило, обладают различнымидополнительными структурными свойствами, которые будутучитываться при описании задач.Стандартная форма описания задач состоит из двухчастей. В первой части дается описание условия задачи втерминах различных компонент - множеств, графов, функций,чисел и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
