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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Задачи распознавания свойств. Классы P и NP.)
(→Задачи распознавания свойств. Классы P и NP. - добавил определение класса NP)
Строка 36: Строка 36:
* <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да".
* <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да".
-
'''Класс полиномиально разрешимых задач''' -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:
+
'''Класс полиномиально разрешимых задач (P)''' -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:
* <math>\exists A</math> такой, что <math>A</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math>
* <math>\exists A</math> такой, что <math>A</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math>
* <math>\exists p(\cdot)</math> -- полином такой, что <math>T_A(n) < p(n)~~,~\forall n \in Z_{+}</math>
* <math>\exists p(\cdot)</math> -- полином такой, что <math>T_A(n) < p(n)~~,~\forall n \in Z_{+}</math>
Строка 45: Строка 45:
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
** найти все маршруты в задаче коммивояжёра
** найти все маршруты в задаче коммивояжёра
 +
 +
'''Класс недетерменированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:
 +
* <math>\exists \hat{A}</math> для НДМТ такой, что <math>\hat{A}</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math>
 +
* <math>\exists p(\cdot)</math> -- полином такой, что <math>\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}</math>
== Теорема об экспоненциальной временной оценке для задач из класса NP. ==
== Теорема об экспоненциальной временной оценке для задач из класса NP. ==

Версия 14:56, 7 июня 2009

Содержание

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

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

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

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

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

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

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

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

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

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

\exists p(.): \forall I \in P |e(I)| < p(e_{1}(I))

Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): L(\Pi, e) = e(Y(\Pi)) = \{s \in \Sigma^*| s = e(I), I \in Y(\Pi)\}

Язык алгоритма -- множество слов, принимаемых A, то есть таких, на которых алгоритм останавливается в состоянии qY, что соответсвует "да": L(A) = \{\sigma \in \Sigma^* | A(\sigma) = q_Y\}

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

tA(s) -- число шагов алгоритма A для входа s \in \Sigma^*.

Временная сложность T_{A}(n) = max \{t_{A}(s)\}, s \in \Sigma^*, |s| < n .

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

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

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

Класс полиномиально разрешимых задач (P) -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:

  • \exists A такой, что A решает массовую задачу Π с кодировкой e
  • \exists p(\cdot) -- полином такой, что T_A(n) < p(n)~~,~\forall n \in Z_{+}

Примеры неполиномиальных задач:

  • алгоритмически неразрешимые задачи: \forall A ~~ \exists I \in \Pi такая, что A не применим к I, например, t_A(e(I)) = \infty
    • 10-я проблема Гильберта: по данному многочлену g с целыми коэффициентами выяснить, имеет ли уравнение g = 0 целочисленное решение
  • задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
    • найти все маршруты в задаче коммивояжёра

Класс недетерменированно полиномиальных задач (NP) -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:

  • \exists \hat{A} для НДМТ такой, что \hat{A} решает массовую задачу Π с кодировкой e
  • \exists p(\cdot) -- полином такой, что \hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}

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

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

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

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

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

Получено с http://esyr.name/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%A2%D0%B5%D0%BE%D1%80%D0%BC%D0%B8%D0%BD
Разделы