Теормин

Введение в теорию сложностиИндивидуальная и массовая задачи, кодировка задачи,алгоритм решения массовой задачи, временная сложностьалгоритма.Методичка, стр. 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).Временная сложность.Задачи распознавания свойств.

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

11Для любойсуществует ДМТ A, решающая ее с не более чемэкспоненциальной временной сложностью:.Класс 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-полных задач.Критерий NP-полноты. Д-во NP-полноты задачи ЦЛНМетодичка, стр. 15Критерий NP-полноты.

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

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

Теорема о связи сильной NP-полнотызадачи с существованием псевдополиномиального алгоритмаее решенияПолиномиальное сужение массовой задачи Π -- множество таких индивидуальныхзадач I, числовые параметры которых не превосходят полинома от длины входа:Массовая задача Π называется сильно NP-полной, если её полиномиальное сужениеявляется NP-полным. Примеры:▪задача выполнимости, задача 3-выполнимости -- совпадают со своимиполиномиальными сужениями▪ задача булевых линейных неравенств -- ВЫП сводится к её полиномиальноусужению, где числовые параметры (правая часть неравенств) линейны.▪ задача о целочисленном решении системы линейных уравнений -- , т.к.

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

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

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

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