Методы Оптимизации, Теормин
Материал из eSyr's wiki.
м (→Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения) |
м (→Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения) |
||
Строка 103: | Строка 103: | ||
=== Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | === Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | ||
- | '''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I) \}</math> | + | '''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I|) \}</math> |
Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. | Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. | ||
Строка 110: | Строка 110: | ||
* задача о целочисленном решении системы линейных уравнений | * задача о целочисленном решении системы линейных уравнений | ||
* задача комивояжа | * задача комивояжа | ||
- | |||
=== Определение ?-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью === | === Определение ?-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью === |
Версия 18:20, 7 июня 2009
Введение в теорию сложности
Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма.
Массовая задача Π:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
Π есть множество индивидуальных задач . Индивидуальная задача получается, если всем параметрам присвоить конкретные значения.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: называется кодировкой задачи П.
Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи :
- A применим к I, то есть останавливается за конечное число шагов
- A дает решение I
Кодировка задачи P -- такое отобраение , обладающее следующими свойствами:
- Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
- e,e − 1 -- полиномиально вычислимы
- Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:
Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):
Язык алгоритма -- множество слов, принимаемых A, то есть таких, на которых алгоритм останавливается в состоянии qY, что соответсвует "да":
Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = L(A)
tA(s) -- число шагов алгоритма A для входа .
Временная сложность .
Задачи распознавания свойств. Классы P и NP.
Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.
- D(Π) -- множество всех возможных значений параметров массовой задачи.
- Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".
Класс полиномиально разрешимых задач (P) -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:
- такой, что A решает массовую задачу Π с кодировкой e
- -- полином такой, что
Примеры неполиномиальных задач:
- алгоритмически неразрешимые задачи: такая, что A не применим к I, например,
- 10-я проблема Гильберта: по данному многочлену g с целыми коэффициентами выяснить, имеет ли уравнение g = 0 целочисленное решение
- задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
- найти все маршруты в задаче коммивояжёра
Класс недетерменированно полиномиальных задач (NP) -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:
- для НДМТ такой, что решает массовую задачу Π с кодировкой e
- -- полином такой, что
Теорема об экспоненциальной временной оценке для задач из класса NP.
Для любой существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: .
Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.
Дополнительная задача к массовой задаче Π -- задача, получаемая из Π путем введения альтернативного вопроса. То есть если в Π спрашиваем "верно ли x", то в спрашиваем "верно ли, что "
Класс co-P --
- co-P = P.
Класс co-NP -- .
- co-NP = NP пока не удалось ни доказать, ни опровергнуть.
Массовая задача Π допускает хорошую характеристику, если
- пример такой задачи -- это задача определения простоты числа.
Массовая задача Π' с кодировкой e' полиномиально сводится к задаче Π с кодировкой e, если любая индивидуальная задача может быть сведена за полиномиальное от её длины время к некоторой задаче с сохранением ответа.
Массовая задача Π называется NP-полной (универсальной), если
- принадлежит классу NP:
- любая задача из NP полиномиально сводится к Π:
Класс NPC (NP-complete) -- множество всех NP-полных задач.
Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН
Д-во NP-полноты задачи 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))), где -- некоторый полином от двух переменных.
Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения
Полиномиальное сужение массовой задачи Π -- множество таких индивидуальных задач I, числовые параметры которых не превосходят полинома от длины входа:
Массовая задача Π называется сильно NP-полной, если её полиномиальное сужение является NP-полным.
- задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями
- задача булевых линейных неравенств
- задача о целочисленном решении системы линейных уравнений
- задача комивояжа
Определение ?-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью
Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания
Основы линейного программирования
Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП
ЛП:
(1)Ax < = b,x = {xi},i = 1...n, существует ли , удовлетворяющий данной системе линейных неравентсв
озЛП:
найти такой -- решение (1) и
Утверждение (принцип граничных решений). Если озЛП имеет решение, то найдется такая подматрица AI матрицы А, что любое решение системы уравнений AIx = bI реализует максимум c(x).
Алгебраическая сложность - количество арифметических операций.
Битовая сложность - количество операций с битами. Битовая сложность задач ЛП, ЛН полиномиальна.
Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым.
Теорема о границах решений задач ЛП с целыми коэффициентами
dt(D) = max | det(D1) | , где D_1 -- квадратная подматрица D
Если задача озЛп размерности (n, m) с целыми коэффициентами разрешима, что у нее существует рацональное рашение x * в шаре: и
Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами
Определение. xε -- ε-приближенное решение системы ЛН, если < ai,xε > < = bi + ε
Теорема. Если система линейных неравенств имеет ε1 приближенное решение (), то эта система разрешима, то есть имеет точное решение.
Описание метода эллипсоидов
Лемма1.Если система Ax <= b совместна,то в шаре найдется ее решение.
Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений