Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

вершин этого графа, то за п шагов легко определяется, порождает она гамиль- тонов цикл или нет. По аналогии можно думать, что в классе NP имеются зада­ чи, которые нельзя решить за полиномиальное время. В теории NP- полноты рассматриваются только задачи разрешения - зада­ чи, в которых требуется дать ответ "да" или "нет" на некоторый вопрос. Фор­ мально задачу разрешения можно рассматривать как функцию, отображающую множество условий i в множество {0,1} (1 = "да", О = "нет"). Многие задачи можно тем или иным образом преобразовать к такому виду. Например, с зада­ чей поиска кратчайшего пути в графе связана задача разрешение ПУТЬ - "по заданному графу G={V,X), паре вершин М,УПКИ натуральному числу к опреде­ лить, суш,ествует ли в G путь между вершинами м и v, длина которого не пре­ восходит F'. Пусть четверка i=<G, и, v, к> является условием задачи ПУТЬ. То­ гда ПУТЬ(/)=1, если длина кратчайшего пути между вершинами м и v не пре­ восходит к, и ПУТЬ(/)=0 в противном случае. В задачах оптимизации требуется минимизировать или максимизировать значение некоторой величины. Прежде чем ставится вопрос о ТУР-полноте та­ ких задач, их следует преобразовать в задачу разрешения. Обычно в качестве такой задачи разрешения рассматривают задачу проверки, является ли некото­ рое число верхней (или нижней) границей для оптимизируемой величины. Так, например, мы перешли от задачи оптимизации КРАТЧАИШИИ-ПУТЬ к задаче разрешения ПУТЬ, добавив в условие задачи границу длины пути к. Если после этого получается NP- полная задача, то тем самым установлена трудность ис­ ходной задачи. В самом деле, если для оптимизационной задачи имеется быст­ рый алгоритм, то и полученную из нее задачу разрешения можно решить быст­ ро (надо просто сравнить ответ этого алгоритма с заданной границей). Таким образом, теорию ТУР-полноты можно использовать и для исследования задач оптимизации. § 5. Л^Р-полные и Л^Р-трудные задачи Рассмотрим сводимость задач. Хотя сведение одних задач к другим явля­ ется традиционной математической деятельностью, до работ С. Кука оно не было подвержено самостоятельному исследованию. Именно С. Куку принадле­ жит честь выделения этого понятия как центрального в теории полиномиальной сводимости. Говорят, что задача Zi сводится к задаче Z^, если метод решения задачи можно преобразовать в метод решения задачи Z^. Сводимость называется поли­ номиальной, если указанное преобразование можно осуш,ествить за полиноми­ альное время. Если одновременно задача Zi полиномиально сводится к задаче Z2^aZ2 поли­ номиально сводится к задаче Z7, то задачи Z7 и Z^ полиномиально эквивалентны. Задача называется NP-трудной, если каждая задача из NP полиномиально сводится к ней. 228