Книги и конспекты / Шпоры / 29-31
.pdfТеория сложности вычислений и сложностные классы задач. Теоритический предел трудоемкости задачи.
NOTE: не уверен, что первая (то, что ниже) часть будет нужна на экзамене. Можете переходить к самим классам задач (чуть ниже).
Рассматривали трудоемкости алгоритма.
ЗадачаD Da
A1 — алгоритм решения.
FА1(D) — в худшем случае. FА1(D)=O(g(n)) — ограничиваем сверху.
Задача A2
FA2(D)=O(g2(n))
и т. д.
Какова l самого быстрого алгоритма в худшем случае, т. е. Существует ли g*, что:
F*(D) = O(g*)
Функциональный нижний предел для f.
Если такой предел существует, то существует ли алгоритм.
Какова оценка сложности самого быстрого алгоритма выполнения данной задачи в худшем случае.
Функциональный нижний теоретический предел трудоемкости залачи в худшем случае
Flim = min(Θ(Fa(D))) = min(Θ(O(g(n)))) (где последнее n = |D|)
Flim = Θ(n) a1,...,an
Пример:
(n(x) + (n-1)(+)) n*n = 2n3 — n2 = Θ(n3) ≠ Flim
Flim = Θ(n2) — теоритический нижний предел На практике F = Θ(n2,34)
Либо не существует более быстрого алгоритма,
либо Θ(n2,34), — нужно докащать, что теоритический нижний предел.
Сложностные классы задач.
Сложностные классы задач отвечают на вопрос, решается ли задача на ЭВМ за конечное f.
1. Задачи с полиноминальной сложностью (класс P).
D P, если она решается, если существует константа l, трудоемкость алгоритма равна O(nk)
Fa(n) = O(nk)
Эта задача реально решаема за конечное время.
Обычно задачу относят к классу P(к полиноминальной задаче), если K≤6.
D1 P,D2 P, то для любой суперпозиции, +, * и др. также задача с полиноминальной сложностью.
P — естественно замкнут.
2. Полиноминально-проверяемые задачи
(класс NP).
В отличие от полиноминальных задач, проверяются за определенное время.
D NP, A1 — алгоритм, R — решение задачи.
Существует такое A1, которому на вход дается R, и он проверяет, правильно ли она решена.
(a1,...,an), {x1,..,xn}, xqXq {0,1}
Найти X:
∑XiAi=V
Пусть R — решение X. n(x) + (n-1)(+) = O(n)
То алгоритм cNP
Задача полиноминально-проверяема.
ДляD Da , |D| = n, существует A и существует — проверяющий правильность.
F() = O(nk)
|
|
|
|
|
|
|
|
3. Класс |
|
|
|
|
|
|
|
|
|
NPC (NP- |
|
|
|
|
|
|
|
|
|
полные |
|
|
|
|
|
|
|
|
|
задачи) |
|
|
|
|
|
|
|
|
|
Задача 1: |
|
|
|
|
|
|
|
|
|
Задача 2: |
|
|
D1 |
|
Da1 |
, A1 |
|
D2 |
|
Da2 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
Алгоритм не существует, |
|
||
|
|
|
|
|
|
но существует , который |
|
||
|
|
|
|
|
|
позволяет сформулировать |
|
||
|
|
|
|
|
|
2 в терминах задачи 1. |
|
||
|
|
|
|
|
|
f(D2) = D1 |
|
||
|
|
|
|
|
|
F(d2) = D1 |
|
||
|
|
|
|
|
|
d — постановка задачи |
|
||
|
Если при этом: |
|
|
|
|
|
|||
Fa(f(d2) = d1) = O(nk) |
|
|
|
|
|
тогда задача 2 полиноминально сводится к 1.
Задача сведения P
Задача 1 принадлежит классу NPC, при этом она должна
принадлежать классу NP.
Теорема
Если
существует задача 1,
принадлежащая классу NPC, которая решается за конечное число шагов (ξ P, F = O(nk)), т. е. NPC∩P ≠ 0,
тогда P=NP