Методы Оптимизации, Теормин

Материал из eSyr's wiki.

Содержание 1 Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма. 2 Задачи распознавания свойств. Классы P и NP. 3 Теорема об экспоненциальной временной оценке для задач из класса NP. 4 Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.

Массовая задача П:

• список свободных параметров;
• формулировка свойств, которым должно удовлетворять решение задачи.

P есть множество индивидуальных задач . Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.

Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: называется кодировкой задачи П.

Алгоритм А решает массовую задачу П, если для любой  : А применим к I, то есть останавливается за конечное число шагов .

Кодировка задачи P: Отобраение , обладающее следующими свойствами:

• Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
• e,e ^{− 1} -- полиномиально вычислимы
• Кодировка не избыточна, то есть для любой другой кодировки e₁, удовлетворяющей 1 и 2 условиям справедливо:

Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):

Язык алгоритма -- множество слов, принимаемых А

Алгоритм A решает массовую задачу П, с кодировкой e, если L(e,P) = L(A)

tA(s) - число шагов алгоритма А для входа (число шагов).

Временная сложность .

Задачи распознавания свойств. Классы P и NP.

Задача расползавания свойств: Это задачи ответ на которые должен быть -- "да", "нет"

Из ИЗ выделим такие задачи, которые дают ответ -- "да". Обозначим множество таких задач -- Y

Пусть D -- всевозможное значенте параметров задачи.

Формально ЗРС определяются следующей парой: [D(П), Y(П)]

Класс полиномиально разрешимых задач

Это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом.

Например, к таким задачам отосится задача распознавания четности числа.

Теорема об экспоненциальной временной оценке для задач из класса NP.

Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: T_A(n) < = 2^p(n).

Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

Задачи, допускающие хорошую характеристику -- это хадачи, входящие в класс: пересечение NP и co-Np

Пример такой задачи -- это задача определения простоты числа.