Теормин (Esyr)

Введение  в  теорию  сложности1) Индивидуальная  и  массовая  задачи,  кодировка  задачи,  алгоритм  решения  массовой  задачи,  временная  сложность  алгоритма.Методичка,  стр.  4-8Массовая  задача Π: список  свободных  параметров;; формулировка  свойств,  которым  должно  удовлетворять  решение  задачи.Π есть  множество  индивидуальных  задачпараметрам  присвоить  конкретные  значения.. Индивидуальная  задача получается,  если  всем  Пусть Σ — конечный  алфавит,  а Σ * — множество  слов  в  этом  алфавите.

 Отображение  e:кодировкой  задачи Π.Алгоритм A решает  массовую  задачу Π,  если  для  любой  индивидуальной  задачи A применим  к I,  то  есть  останавливается  за  конечное  число  шагов A дает  решение Iназывается  :Кодировка  задачи  P — такое  отображение,  обладающее  следующими  свойствами: Возможность  однозначно  декодировать,  то  есть  у  двух  различных  ИЗ  не  может  быть  одинаковых  кодировок. e,e −  1 — полиномиально  вычислимы Кодировка  не  избыточна,  то  есть  для  любой  другой  кодировки e1,  удовлетворяющей  1  и  2  условиям  справедливо:Язык  массовой  задачи — это  множество  правильных  слов,  то  есть  слов,  соответствующих  ИЗ,  имеющим  положительный  ответ(подразумевается  задача  распознавания):Язык  алгоритма — множество  слов,  принимаемых A,  то  есть  таких,  на  которых  алгоритм  останавливается  в  состоянии qY,  что  соответсвует  "да":Алгоритм A решает массовую  задачу Π,  с  кодировкой e,  если L(e,Π)  = L(A) иЧисло  шагов алгоритма A для  входаА  останавливается— это tA(s).Временная  сложность.2) Задачи  распознавания  свойств.

 Классы  P  и  NP.Методичка,  стр.  8-11Задача  распознавания  свойств -- массовая  задача,  предполагающая  ответ  "да"  или  "нет",  в  качестве  своего  решения. D(Π) -- множество  всех  возможных  значений  параметров  массовой  задачи. Y(Π) -- множество  всех  индивидуальных  задач,  ответом  на  которые  является "да".Класс  полиномиально  разрешимых  задач  (P) -- это  такие  задачи,  временная  сложность  алгоритма  решения  которых  ограниченна  полиномом:такой,  что A решает  массовую  задачу Π с  кодировкой e-- полином  такой,  чтоПримеры  неполиномиальных  задач:алгоритмически  неразрешимые  задачи:такая,  что A не  применим  к I,например, 10-я  проблема  Гильберта:  по  данному  многочлену g с  целыми  коэффициентами  выяснить,  имеет  ли  уравнение g = 0 целочисленное  решениезадачи,  для  которых  длина  записи  выхода  превышает  любой  наперед  заданный  полином  от  длины  входа найти  все  маршруты  в  задаче  коммивояжёра∀А,  решающего  П  с  кодировкой  e,  ∀p(·)  ∃I ∈ П: tA(e(I)) > p( | e(I) | )Класс  недетерминированно  полиномиальных  задач  (NP) -- это  такие  задачи,  для  которых  существует  алгоритм  решения  на  недерменированной  машине  Тьюринга:для  НДМТ  такой,  чторешает  массовую  задачу Π с  кодировкой e-- полином  такой,  что3) Теорема  об  экспоненциальной  временной  оценке  для  задач  из  класса  NP.Методичка,  стр.

 11Для  любойсуществует  ДМТ A,  решающая  ее  с  не  более  чем  экспоненциальной  временной  сложностью:.4) Класс  co-NP.  Пример  задачи,  допускающей  хорошую  характеризацию.  Доказательство  утверждения  о  взаимоотношении  классов  NPC  и  co-NP.Методичка,  стр.  12-14Дополнительная  задачак  массовой  задаче Π -- задача,  получаемая  из Π путем  введения  альтернативного  вопроса.

 То  есть  если  в Π спрашиваем  "верно  ли x",  то  вспрашиваем  "верно  ли,  что"Класс co-P - co-P = P.Класс co-NP -. co-NP = NP пока  не  удалось  ни  доказать,  ни  опровергнуть,  но  это  вряд  ли  верно.Массовая  задача Π допускает  хорошую  характеризацию,  если пример  такой  задачи  -- это  задача  определения  простоты  числа.Массовая  задача Π' с  кодировкой e' полиномиально  сводится к  задаче Π с  кодировкой e,  если  любая  индивидуальная  задачаможет  быть  сведена  за  полиномиальное  от  её  длины  время  к  некоторой  задачес  сохранением  ответа.Массовая  задача Π называется NP-полной  (универсальной),  еслипринадлежит  классу  NP: любая  задача  из  NP  полиномиально  сводится  к Π:Класс NPC (NP-complete) -- множество  всех  NP-полных  задач.5) Критерий  NP-полноты.

 Д-во  NP-полноты  задачи  ЦЛНМетодичка,  стр.  15Критерий  NP-полноты. Массовая  задача Π NP-полна тогда  и  только  тогда,  когда  она принадлежит  классу NP и  к  ней  полиномиально  сводится  какая-либо NP-полная задача.6) Д-во  NP-полноты  задачи  3-выполнимость.

 NP-трудные  задачиМетодичка,  стр.  17-18Класс NP-трудных задач  содержит:1. задачи  распознавания  свойств Π,  для  которыхне  доказано,  что2. задачи  оптимизации,  для  которых  соответствующие  задачи  распознавания  свойств3. любые  задачи,  к  которым  сводятся  по  Тьюрингу  хотя  бы  одна NP-полная задача7) Взаимоотношение  классов  P,  NP  и  NPC,  NP  и  co-NP.  Класс  PSPACEЛегко  показать,  что.

 Рабочая гипотеза,  что.Если  для  некоторой  NP-полной  задачи Π дополнительная  к  ней  задача,  то NP = co-NPКласс PSPACE массовых  задач  -- класс  алгоритмов,  требующих  не  более,  чем  полиномиальной  памяти.Гипотеза.(то  есть,  не  факт,  что  вложение  строгое,  но  скорее  всего  так).  При  этом  NP-полные,  NP-трудные,  NP-эквивалентные  задачи8) Псевдополиномиальные  алгоритмы.  Пример  для  задачи  о  рюкзакеПсевдополиномиальный  алгоритм - полиномиальный  алгоритм,  проявляющий  экспоненциальный  характер  только  при  очень  больших  значениях  числовых  параметров.Пусть M(I) -- некоторая  функция,  задающая  значение  числового  параметра  индивидуальной  задачи I.

 Если  таких  параметров  несколько,  в  качестве M(I) можно  взять  или  максимальное,  или  среднее  значение,  а  если  задача  вовсе  не  имеет  числовых  параметров  (например,  раскраска  графа,  шахматы  и  т.п.),  то M(I) = 0.  Алгоритм  называется  псевдополиномиальным,  если  он  имеет  оценку  трудоемкости Tmax(I) = O(p( | I | ,M(I))),  гденекоторый  полином  от  двух  переменных.en-wiki--9) Сильная  NP-полнота.  Теорема  о  связи  сильной  NP-полноты  задачи  с  существованием  псевдополиномиального  алгоритма  ее  решенияПолиномиальное  сужение массовой  задачи Π -- множество  таких  индивидуальных  задач I,  числовые  параметры  которых  не  превосходят  полинома  от  длины  входа:Массовая  задача Π называется сильно  NP-полной,  если  её  полиномиальное  сужение  является  NP-полным.

 Примеры: задача  выполнимости,  задача  3-выполнимости  -- совпадают  со  своими  полиномиальными  сужениями задача  булевых  линейных  неравенств  -- ВЫП  сводится  к  её  полиномиальноу  сужению,  где  числовые  параметры  (правая  часть  неравенств)  линейны. задача  о  целочисленном  решении  системы  линейных  уравнений  -- ,  т.к.  БЛН  сводится  к  ней задача  коммивояжёра  (TSL)  -- совпадает  со  своим  сужениемЗадача  о  рюкзаке  -- слабо-NPC.Теорема.  Если  NP  не  совпадает  с  P,  то  ни  для  какой  сильно-NPC  задачи  не  существует  псевдополиномиального  решения.10)Определение  ε-приближенного  алгоритма  и  полностью  полиномиальной  приближенной  схемы  (ПППС).

 Связь  между  существованием  ПППС  и  псевдополиномиальностьюМетодичка,  стр.  22-24Задача  дискретной  оптимизации -- решение  каждой  индивидуальной  задачиявляется  произвольная  реализация  оптимума,  где SΠ(I) -- область  допустимых  значений  дискретной  переменной z fΠ -- целевая  функция  задачи  оптимизации max вообще  говоря  вполне  может  быть  заменён  на minАлгоритм A называется приближённым  алгоритмом решения  массовой  задачи Π,  если  для  любой  задачион  находит  точкуза  приближённое  решение.Утверждение.  Если,  лежащую  в  области  допустимых  значений,  принимаемую  ,  то  ни  для  какой  константы C > 0 не  существует  полиномиального  приближённого  алгоритма  решения  задачи  о  рюкзаке  с  оценкойПриближённый  алгоритм A решения  массовой  задачи Π называетсязадачи,  если..-приближённым  алгоритмом решения  11)Теорема  об  отсутствии  ПППС  для  задач  оптимизации,  соответствующих  сильно  NP-полным  задачам  распознаванияМетодичка,  стр.

 24Теорема Если  для Π оптимизации соответствующая  ей  задача  распознавания  свойств  является  сильно  NP-полнойсуществует  полиномто  при  условии,  чтодля Π не  существует  ПППСОсновы  линейного  программирования12)Определение  озЛП.  Принцип  граничных  решений.  Алгебраическая  и  битовая  сложность  ЛП.  Результаты  о  сложности  для  задач,  близких  к  ЛПЛП (линейное  программирование)  -- теория,  приложения  и  методы  решения  системы  линейных  неравенств  с  конечным  числом  неизвестных :удовлетворяющий  данной  системе  линейных  неравентсв,  существует  лиозЛП (основная  задача  линейного  программирования) :  найти  такой  векторлинейного  программирования,-- решение  задачи  ,  максимизирующее  линейную  функциюУтверждение  (принцип  граничных  решений).  Если  озЛП  имеет  решение,  то  найдется  такая  подматрица AI матрицы A,  что  любое  решение  системы  уравнений AIx = bI реализует  максимум.Алгебраическая  сложность -- количество  арифметических  операций.Битовая  сложность -- количество  операций  с  битами.

 Битовая  сложность  задач  ЛП,  ЛН  полиномиальна.Вопрос  о  существовании  алгебраически-полиномиального  алгоритма  для  ЛП  остается  открытым.13)Геометрическое  описание  симплекс-метода(Копипаста  из  [ru.wiki],  там-же  есть  хорошая  иллюстрация.)Симплекс-метод  -- метод  решения  озЛП.Каждое  из  линейных  неравенств  вограничивает  полупространство в  соответствующем  линейном  пространстве.

 В  результате  все  неравенства  ограничивают  некоторый  многогранник  (возможно,  бесконечный),  называемый  также  полиэдральным  конусом.  Уравнение W(x) = c,  где W(x) — максимизируемый  (или  минимизируемый)  линейный  функционал,  порождает  гиперплоскость L(c).  Зависимость  от c порождает  семейство  параллельных  гиперплоскостей.  Тогда  экстремальная  задача  приобретает  следующую  формулировку  — требуется  найти  такое  наибольшее c,  что  гиперплоскость L(c) пересекает  многогранник  хотя  бы  в  одной  точке.  Заметим,  что  пересечение  оптимальной  гиперплоскости  и  многогранника  будет  содержать  хотя  бы  одну  вершину.  Принцип  симплекс-метода  состоит  в  том,  что  выбирается  одна  из  вершин  многогранника,  после  чего  начинается  движение  по  его  ребрам  от  вершины  к  вершине  в  сторону  увеличения  значения  функционала.