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

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

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

Введение в теорию сложности

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

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

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

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

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

Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи  :

• A применим к I, то есть останавливается за конечное число шагов
• A дает решение I

Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.

• D(Π) -- множество всех возможных значений параметров массовой задачи.
• Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".

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

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

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

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

Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = 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

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