(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 21
Текст из файла (страница 21)
Можно потребовать, чтобы любые величины,сопоставляемыеэлементаммножества,принадлежалинекоторому ограниченному множеству допустимых значений.Из всех этих возможных задач для детального анализаобычно выбираютсяте, которыеимеютизвестныеприложенияиливкаком-тосмыслеявляются«естественными» подзадачами, возникновение которыхможно ожидать в приложениях.Совершенно ясно, что, если даже задача П является NPполной, ее подзадачи могут быть как NP-полными, так иполиномиально разрешимыми. Конечно, если задача ПпринадлежитклассуР, то любаяее подзадача,индивидуальныезадачикоторойраспознаваемызаполиномиальное время (а мы будем рассматривать толькоподзадачи, обладающие последним свойством),Рис. 6.5 Одна из возможных ситуаций состояния знаний о подзадачах NPполной задачи П.
Задачи изображены кружками. Тёмные кружкисоответствуют NP-полным задачам, светлые - задачам класса Р, акружки с точкой - «открытым» задачам Стрелка от задачи П] кзадача ГЬ указывает на то, что ГЬ есть подзадача ГЬ.также должна лежать в Р. Мы уже отмечали отличающиеся вэтом отношении две подзадачи ВЫПОЛНИМОСТЬ:аименно, задачи 3-ВЫПОЛНИМОСТЬ и 2-ВЫПОЛНИМОСТЬ.В предположении, что P^NP можно считать, что подзадачилюбой NP-полной задачи лежат по разные сторонывоображаемойграницы,разделяющейполиномиальноразрешимые и труднорешаемые задачи. При анализе задачнаша цель состоит в выяснении, какие подзадачи по какуюсторону от этой границы лежат.В действительности лучше будет в каждый отдельныймомент времени представлять себе пограничную зону междуподзадачами, разрешимость которых за полиномиальноевремя уже известна, и подзадачами, для которых установленаNP-полнота.
Подобная пограничная зона состоит из подзадач,NP-полнота которых остается под вопросом. На рис. 6.5схематически изображено возможное состояние знаний онаборе подзадач задачи П.Если удаётся определить, что некоторая открытая задачалежит в Р или NP-полна, то тем самым сужается пограничнаязона и увеличивается изученная часть класса NP. Конечно,если задача неразрешима за полиномиальное время, намникогда не удастся полностью исчерпать пограничную зону,кроме, возможно, случая, когда представляет интерес толькоограниченное число подзадач.
Даже когда мы ограничиваемсяфиксированным, конечным набором подзадач, некоторые изнихмогутоказатьсяпринадлежащимикгруппепромежуточных задач, которые ни NP-полны, ни принадлежатклассу Р (как мы уже отмечали, если P^NP, то такие задачидолжны существовать). Тем не менее, когда мы выясняемместо одной из задач, оставшейся открытой, можно считать,что мы приближаемся к воображаемой пограничной линии.Чтобы конкретизировать сказанное выше, рассмотримзадачу составления расписания выполнения заданий,имеющих равную длительность и подчиненных отношениюпредшествования (эта задача сама по себе представляетчастный случай некоторых более общих задач теориирасписаний).РАСПИСАНИЕ С ОТНОШЕНИЕМПРЕДШЕСТВОВАНИЯУСЛОВИЕ.
Задано множество Т «заданий» (предполагается,что все они имеют длительность 1) и частичный порядок < намножестве Т, число «процессоров» m и общий директивныйсрок D e ZВОПРОС. Существует ли «расписание» а : Г-э{0,1,...Д}}, чтодля каждого /е {0,1,...,£> : \{te T:o(t)~i}\< m и если t< t\ тоa(t)< 0(C)}?В качестве возможного приложения этой задачи рассмотрим такую ситуацию. Предположим, что вы ассистенткафедры прикладной математики МГУПС (МИИТа) и толькочто получили задание помочь поступившим первокурсникамсоставить план своих занятий на все время обучения.Студенты представляют вам список всех курсов, которые онинамереваются прослушать, число m - максимальное числокурсов, которые они могут слушать одновременно, и D - числосеместров обучения.
Университет достаточно большой, такчто каждый курс лекций читается каждый семестр и никакиедва курса не пересекаются по времени. Однако некоторыекурсы являются вспомогательными для других и поэтомудолжны быть прослушаны раньше последних (t<t' означает,что t является вспомогательным для /'). Предположим, что вырешили написать программу для ЭВМ, которая, пользуясьэтой информацией, составляла бы для каждого студентасоответствующее расписание.Было доказано, что задача РАСПИСАНИЕ СОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ NP-полна, поэтомумало вероятно, что вам удастся построить полиномиальныйалгоритм составления расписания в общем случае. Тем неменее,возможно, найдутся некоторые естественныеограничения, приемлемые для большинства студентов иоблегчающие решение задачи.
Поскольку работоспособностьстудентов ограничена, то вполне вероятно, что т можноограничить сверху некоторым числом, например 6.Вспомогательные курсы лекций также могут удовлетворятьдополнительным ограничениям. Многие из студентов могливыбрать столь разнообразную программу обучения, что ниодин из выбранных ими курсов лекций не потребуетвспомогательных курсов (в этом случае условие порядкаотсутствует).'"< ! /л< 2 w<34<пршзЗ&ш О—Ю~>®—Hjb< ИереЮ.< agtmТtтт—HL>-5т ^ тщ— н}'Iк !)...аРис. 6.6 Современное состояние знаний о семействе подзадач задачиРАСПИСАНИЕ С ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ(в обозначениях рис. 6.5)Иногда может оказаться, что для каждого данного курсалекций требуется только один явный вспомогательный курс, аостальные курсы, вспомогательные для данного, являютсявспомогательными также и для явного вспомогательного. Вэтом случае частичный порядок представляет собой древовидную структуру. Возможны и другие ограничения, но остановимся только на перечисленных.
Возникает семействоподзадач, представленное на рис.6.6. На этом же рисункеприведены известные сведения о сложности этих подзадач.Заметим, что все возможности, указанные на рис. 6.5, включаяпограничную зону, встречаются на рис.6.6. В случае, когдаимеется подобная однородная иерархия подзадач, очень частоту же самую информацию можно задать более кратко, указав«минимальную» NP-полную и «максимальную» разрешимуюза полиномиальное время подзадачу. Если задано семейство Сподзадач некоторой NP-полной задачи, то задача П еСявляется (в настоящее время) минимальной NP-полнойподзадачей, если известна NP-полнота задачи П и у нее нетподзадачи ГГ, которая была бы NP-полна и принадлежаласемейству С. Задача П еС является (в настоящее время)максимальной полиномиально разрешимой подзадачей, еслиизвестна ее принадлежность классу Р и в семействе С нетзадачи П\ которая была бы разрешима за полиномиальноевремя и содержала бы П в качестве подзадачи.
Аналогичнымобразом можно определить минимальную и максимальнуюоткрытые подзадачи семейства С.Для класса подзадач задачи РАСПИСАНИЕ СОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ, представленного нарис. 6.6, две подзадачи, определяемые ограничениями «< произвольно, т< 2» и «< - дерево, т - произвольно», являлисьна 1982г.
максимальными подзадачами, разрешимыми за полиномиальное время. Сама общая задача являлась На 1982 г.минимальной NP-полной подзадачей. Минимальная открытаяподзадача определяется ограничениями «< - произвольно,гп<3», а максимальной открытой подзадачи не существует,поскольку все задачи с ограничением вида «< - произвольно,т < / » открыты при всех целых ,/> 3.Вполнеестественнымпредставляетсяизучениепограничной области задачи с помощью общей схемыдвустороннего подхода, описанной выше.
По очередирассматриваются подзадачи, представляющиеся наиболеевероятными кандидатами на принадлежность классу Р, иподзадачи, кажущиеся NP-полными. Используя в качествеотправных точек подзадачи, разрешимые за полиномиальноевремя, и подзадачи,NP-полнота которых следуетнепосредственно из NP-полноты общей задачи, мыпостепенно увеличиваем множество индивидуальных задачпервой подзадачи и уменьшаем множество индивидуальныхзадач второй. В отличие от случая, когда изучается однаотдельная задача с переходами от построения алгоритма кдоказательству NP-полноты, при анализе подзадач у наспоявляется возможность изменять также и сами задачи, отболее ограничительных к менее ограничительным.Техника, используемая для доказательства NP-полнотыподзадач, по существу аналогична описанной ранее техникедоказательства NP-полноты изолированных задач.
Однакоимеется весьма важное различие. Когда мы пытаемся доказатьNP-полноту подзадачи, нам уже известно доказательство NPполноты некоторой обобщенной версии этой подзадачи. Этодает нам хорошего кандидата на известную NP-полную задачу(чем можно воспользоваться в искомом доказательстве), атакже доказательство NP-полноты, которое можно было бымодифицировать,чтобыполучитьсоответствующеедоказательство для рассматриваемой подзадачи. Хотя это и невсегда облегчит достижение нашей цели, но, по крайней мере,в отличие от доказательства NP-полноты изолированнойзадачи, нам будет от чего оттолкнуться.ЛИТЕРАТУРАГГэри М., Джонсон Д.
Вычислительные машины и труднорешаемые задачи. М., Мир, 1982.2 .Кузюрин Н.Н.Лекции по курсу «Сложность комбинаторныхалгоритмов». Препринт, июнь 2002.3. Крупский В.Н. Введение в сложность вычислений. М., ФАКТОРИАЛ ПРЕСС, 2006, 128 С.4. Учебное пособие по курсу «Сложность алгоритмов». МГУимени М.В.Ломоносова, факультет ВМК, М., 2002.б.Сапоженко А.А. Некоторые вопросы сложности алгоритмов.МГУ имени М.В.Ломоносова, факультет ВМК, М., 2001.6. Нечаев В.И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
