Теорія Складності Обчислень:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Теорія Складності Обчислень

Теорія Складності Обчислень:Колоквіум

Питання до іспиту

Зміст

1 Часова та просторова складностi алгоритмiв обчислення функцiй та предикатiв. Вживання символiки O(f(n))
2 Поняття бiтової операцiї, часова складнiсть алгоритмiв додавання, множення, дiлення з остачею, пiднесення до степеня в кiльцi лишкiв
3 Клас P
4 Часова складнiсть розширеного алгоритму Евклiда
5 Булева схема, схемна складнiсть, клас P/poly
- 5.1 P ≠ P/poly
6 Довести включення P ⊂ P/poly i показати, що воно є строгим
7 Недетермiнована машина Тюринга, клас предикатiв NP. Предикатне означення класу NP, еквiвалентнiсть цих означень
8 Теорема Гауса - при яких група є циклічною
9 Полiномiальна звiднiсть ї ї властивостi. Поняття NP− повного предиката
10 Предикат SAT. Теорема Кука
11 Теорема Кука
12 Приклади рiзних NP− повних проблем, що отримуються через полiномiальну звiднiсть
13 Цілочисельне лінійне програмування (JLP)
14 Ймовiрноснi алгоритми, клас предикатiв BPP, машинне та предикатне означення
15 Ймовiрносний алгоритм перевiрки простоти числка. Довести, що вiн належить класу BPP
16 Довести включення BPP ⊂ P/poly
17 Класи складностей Σ_k,Π_k
18 Довести включення BPP ⊂ Σ₂ ∩ Π₂
19 Критерiй належностi предиката до класу PSPACE
20 TQBF предикат та його PSPACE повнота

Часова та просторова складностi алгоритмiв обчислення функцiй та предикатiв. Вживання символiки O(f(n))

Целью анализа трудоёмкости алгоритмов является нахождение оптимального алгоритма для решения данной задачи. В качестве критерия оптимальности алгоритма выбирается трудоемкость алгоритма, понимаемая как количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.

Трудоёмкость алгоритмов по-разному зависит от входных данных. Для некоторых алгоритмов трудоемкость зависит только от объема данных, для других алгоритмов — от значений данных, в некоторых случаях порядок поступления данных может влиять на трудоемкость. Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.

Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

Основной оценкой функции сложности алгоритма f(n) является оценка $\boldsymbol{\Theta}$ . Здесь n — величина объёма данных или длина входа. Мы говорим, что оценка сложности алгоритма

$f(n) = \boldsymbol{\Theta}(g(n))$

если при g > 0 при n > 0 существуют положительные с₁, с₂, n₀, такие, что:

$c_1 g(n)\le \; f(n) \le \; c_2 g(n)$

при n > n₀, иначе говоря, можно найти такие с₁ и c₂, что при достаточно больших n f(n) будет заключена между

$\boldsymbol{c_1\;g(n)}$ и $\boldsymbol{c_2\;g(n)}$ .

В таком случае говорят еще, что функция g(n) является асимптотически точной оценкой функции f(n), так как по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки heapsort оценка трудоёмкости составляет

$f(n) = \boldsymbol{\Theta}(n \log n)$ то есть $g (n) = n log n$

Из $f(n) = \boldsymbol{\Theta}(g(n))$ следует, что $g(n) = \boldsymbol{\Theta}(f(n))$ .

Важно понимать, что $\boldsymbol{\Theta}(g(n))$ представляет собой не функцию, а множество функций, описывающих рост $\boldsymbol{f(n)}$ с точностью до постоянного множителя.

$\boldsymbol{\Theta}$ дает одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка $\boldsymbol{O}$ представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Мы говорим, что $f(n)=\boldsymbol{O}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; f(n) \le \; c g(n), \forall \; n > n_0$

Иначе говоря, запись $f(n) = \boldsymbol{O}(g(n))$ означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

Оценка $\boldsymbol{\Omega}$ задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. $f(n)=\boldsymbol{\Omega}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; c g(n) \le \; f(n), \forall \; n > n_0$

Например, запись $f(n)=\boldsymbol{\Omega} (n \log \; n)$ обозначает класс функций, которые растут не медленнее, чем $\boldsymbol{g(n) = n \log \; n}$ , в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы. Равенство $f(n) = \boldsymbol{\Theta}(g(n))$ выполняется тогда и только тогда, когда $f(n)=\boldsymbol{O}(g(n))$ и $f(n)=\boldsymbol{\Omega}(g(n))$ .

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее $\boldsymbol{\Omega}(n \log n)$ .

Важную роль в развитии асимптотического анализа алгоритмов сыграли A. Ахо, Дж. Ульманом, Дж. Хопкрофт.

http://ru.wikipedia.org/wiki/Теория_алгоритмов

Розглядаючи вхідні дані достатньо великих розмірів для оцінки такої величини, як порядку росту часу роботи алгоритму ми тим самим вивчаємо асимптотичну ефективність алгоритмів. Це означає, що нас цікавить тільки те, як час роботи алгоритму зростає, коли розмір вхідних даних прямує до нескінченності. За звичай алгоритм, більш ефективний в асимптотичному смислі, буде більш ефективним для всіх вхідних даних за винятком хіба що дуже малих.

$\boldsymbol{\Theta}$ - позначення

Для деякої функції $g (x)$ запис $\boldsymbol{\Theta}(g(n))$ означає множину функцій $\boldsymbol{\Theta}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c_1 > 0, c_2 > 0, n_0 > 0 \\ 0 \le \; c_1 g(n)\le \; f(n) \le \; c_2 g(n), n \ge n_0 \end{Bmatrix}$

Функція $f (n)$ належить $\boldsymbol{\Theta}(g(n))$ , якщо існують додатні константи $c 1$ та $c 2$ , такі що вона буде обмежена функціями $c 1 g (n)$ та $c 2 g (n)$ для достатньо великих n. Оскільки $\boldsymbol{\Theta}(g(n))$ це множина, то можна написати $f(n) \in \boldsymbol{\Theta}(g(n))$ . Для цього зазвичай використовують еквівалентне позначення $f(n) = \boldsymbol{\Theta}(g(n))$ . Знак дорівнює для позначення належності множині може збивати з пантелику, але як буде видно далі це має свої переваги. Кажуть, що функція $g (n)$ є асимптотично точною оцінкою функції $f (n)$ . Відповідно до означення множини $\boldsymbol{\Theta}(g(n))$ , потрібно щоб кожен її елемент $f (n)$ був асимптотично невідємним. Це означає, що при достатньо великих $n$ функція $f (n)$ є невідємною. Відповідно функція $g (n)$ має бути асимптотично невідємною, оскільки в протилежному випадку множина $\boldsymbol{\Theta}(g(n))$ буде порожньою.

Доведемо, що має місце $n^2/2 - 3n = \boldsymbol{\Theta}(n^2)$ за допомогою формального означення. Для цього потрібно визначити чому дорівнюють додатні константи $c 1$ , $c 2$ та $n 0$ , щоб виконувалась нерівність $c_1n^2\le \; n^2/2 - 3n \le \; c_2n^2$ , при всіх $n_0\le \;n$ . Поділивши дану нерівність на $n 2$ , отримаємо: $c_1\le \; \frac{1}{2} - \frac{3}{n} \le \; c_2$ . Права нерівність виконується при всіх $n \ge 1$ , якщо обрати $c_2 \ge \frac{1}{2}$ . Аналогічно, ліва нерівність виконується при всіх $n \ge 7$ , якщо обрати $c_1 \le 14$ . Таким чином, обравши $c_1=\frac{1}{14}, c_2 = \frac{1}{2}, n_0 = 7$ , переконуємось в тому, що $n^2/2 - 3n = \boldsymbol{\Theta}(n^2)$ .

Також за допомогою формального означення покажемо, що $6n^3 \ne \boldsymbol{\Theta}(n^2)$ . Від супротивного...Припустимо, що знайдуться такі $c 2$ та $n 0$ , що $6n^3 \le c_2n^2$ для всіх $n \ge n_0$ . Тоді, виходить, що $n \le c_2/6$ , а ця нерівність не може виконуватись для великих $n$ , оскільки $c 2$ є константою. Суперечність...

$\boldsymbol{O}$ - позначення

В $\boldsymbol{\Theta}(n^2)$ - позначенні функція асимптотично обмежена зверху і знизу. Якщо досить визначити тільки асимптотично верхну межу використовують $\boldsymbol{O}$ -позначення. Для деякої функції $g (n)$ позначення $\boldsymbol{O(g(n))}$ означає множину функцій таких, що $\boldsymbol{O}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c > 0, n_0 > 0 \\ 0 \le f(n) \le cg(n), n \ge n_0 \end{Bmatrix}$ .

Щоб вказати, що функція $f (n)$ належить множині пишуть $f(n) = \boldsymbol{O(g(n))}$ . Також варто звернути увагу на те, що із $f(n) = \boldsymbol{\Theta}(g(n))$ випливає, що $f(n) = \boldsymbol{O}(g(n))$ , оскільки $\boldsymbol {\Theta}(g(n)) \subset {O}(g(n))$ .

$\boldsymbol{\Omega}$ - позначення

Аналогічно тому як для $\boldsymbol{O}$ дається асимптотична верхня межа функції, в $\boldsymbol{\Omega}(g(n))$ -позначеннях дається її асимптотична нижня оцінка. Для даної функції $g (n)$ позначення $\boldsymbol{\Omega(g(n))}$ означає множину функцій таких, що $\boldsymbol{\Omega}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c > 0, n_0 > 0 \\ 0 \le cg(n) \le f(n), n \ge n_0 \end{Bmatrix}$ .

Теорема. Для довільних двої функцій $f (n)$ та $g (n)$ співвідношення $f(n) = \boldsymbol{\Theta}(g(n))$ , виконується тоді і тільки тоді, коли $f(n) = \boldsymbol{O}(g(n))$ та $f(n) = \boldsymbol{\Omega}(g(n))$ .

Поняття бiтової операцiї, часова складнiсть алгоритмiв додавання, множення, дiлення з остачею, пiднесення до степеня в кiльцi лишкiв

Бітова операція

Додавання

$n \rightarrow ln n$
$n+m \rightarrow$

length(n)=k

length(m)=l

length(m+n)=max(k,l)+1

Додавання k чисел завдовжки:

$length(\sum_{i=1}^k n) = l+k=lg n +k$

Множення:

l e n g t h (n) = k

l e n g t h (m) = l

$length(n \cdot m)=O(k+l)$

$2^{k-1} \le n \le 2^k$

$2^{l-1} \le m \le 2^l$

$2^{(k-1)+(l-1)} \le n \cdot m \le 2^{k+l}$

f(n)=O(g(n))

$\exists c \exists n_0 \forall n > n_0$
$f(n) \le c g(n)$

$time(m \cdot n)=O(ln m \cdot ln n)$

Приклади

$n 4 + 25 n 2 + 40$

O (4 l n n)

$a_{k}n^k+a_{k-1}n^{k-1}+ \dots + a_{1}n+a_0$

Клас P

Функція або предикат належить класу P (f, L є P), якщо кількість кроків, які робить мшина Тьюринга T(|x|) є поліномом від |x|.

PSPACE визначається через кількість комірок, які задає машина Тьюринга для вхідних даних.

f(|x|) -кількість задіяних комірок.

Якщо f(|x|) - залежить поліноміально від |x|, то f або L є PSPACE.

$P \subset PSPACE$

Часова складнiсть розширеного алгоритму Евклiда

Булева схема, схемна складнiсть, клас P/poly

f=(f₁, f₂, ..., f_n)

f_i - булеві функції

f - повна система зв'язок

y₁, y₂, ..., y_s - допоміжні змінні

S - булева схема визначається сукупністю операторів присвоєння.

$\tilde{f} \ni f_{\tau}$ операція з базису

$y i : = f τ (H i 1,..., H i r)$ операція з базису

H_ij - початкові змінні або допоміжні змінні з меншим номером

Результати обчислення: беремо останні m присвоювань

Розмірність схеми: називається кількість операторів присвоєння.

Булева схема обчислює f(x), якщо для будь-якого x результатом присвоювань буде значення цієї функції в точці x.

--- $P / p o l y$ Розглянемо функцію яка діє на двійкових стрічках

$f: {0,1}^* \rightarrow {0,1}$

{0,1^*- множина всіх слів в алфавіті

$f \rightarrow f_n = f_n(x_1, \dots, x_n)$

f_n - предикат

$C (f n)$ - розмір відповідної булевої схеми (складність)

Предикат $f \in P/poly$ , якщо $C (f n)$ росте як поліном від (n)

P ≠ P/poly

$φ(n)$ - не обчислюється за поліноміальний час, не рекурсивна

$\forall (x_1, ..., x_n)$ визначаємо $f φ (x) = φ( | x | )$ на всіх x, які мають однакову довжину, значення будуть однакові

Кільість присвоювань - для кожного n - const

$\phi(n) \in P/poly$ , але не належить P

Доведено

Теорема $f \in P \Leftrightarrow$

1) $f \in P/poly$

2) існує машина Тьюринга, яка по числу n за час poly(n) будує схему обчислення

f n

Довести включення P ⊂ P/poly i показати, що воно є строгим

Теорема

Клас $P \subset P/poly$

Доведення

Припустимо, що $f \in P$ , тоді існує машина Тьюринга за T(|x|)

q_j - стан управляючого пристрою, якщо він знаходиться під коміркою Інакше 0.

По цій таблиці можна побудувати булеву функцію:

залежить від трьох верхніх значень (через систему присвоювань обраховуємо)

$O(T(|x|) \ cdot S(|x|)$ - кількість присвоювань, тобто $C (f n)$ росте як поліном від (n). Тобто, $f \in P/poly$ .

Доведено

Недетермiнована машина Тюринга, клас предикатiв NP. Предикатне означення класу NP, еквiвалентнiсть цих означень

Задача $L_x(n)= \begin{cases} 1, if n - complex \\ 0, if n - simple \end{cases}$ належить до класу NP.

Якщо істинність можна перевірити за поліноміальний час

NP визначається тільки для предикатів.

Означення

$L \in NP, \exists HMT, polinom p(H)$ : існує шлях обчислення, який дає відповідь "так" за час ≤ p(|x|) L(x) = 0 => такого шляху не існує

Означення 2 (еквівалентне)

Предикат $L \in NP$ якщо його можна подати в такому вигляді:

$L(x)=\exists y((|y|<q|x|)\land R(x,y))$ :

$R \in P$
q - поліном
K, co-K
$L \in K, \lnot L \in co-K$
$L \in K, \lnot L \in co-P$ =>
$P = c o - P$

"X є простим числом є co-NP"

$L \in NP$

$\lnot L \in co-NP$

$L (x)$ - x є простим числом, є NP

$Z_n^*$ -мультиплікативна група, кільце лишків за mod n

Теорема Гауса - при яких група є циклічною

$Z p$ - поле, (<=> коли p просте число)

Теорема Гауса :

$Z_n^*$ циклічна тоді і тільки тоді:

n=2
n=4
n=2*p^m, p ≠ 2
n=p^m

Пред'явити ξ, яке ξ²... ≠ 1 і всі різні

ξ^n-1=1

Перевірити за Т. Гауса, що не підходтиь умови, потім пред'явити ξ який породжує циклічну групу. А це можливо тільки коли p-просте.

Полiномiальна звiднiсть ї ї властивостi. Поняття NP− повного предиката

$L_1 \varpropto L_2, if \exists f \in P$ : $\forall L_1(n)=L_2(f(n))$

Лема

а) $L_2 \in P \Rightarrow L_1 \in P$

б) $L_1 \notin P \Rightarrow L_2 \notin P$

в) $L_2 \in NP \Rightarrow L_1 \in P$

y = f (n)

для L₂, для L₁ y=n

$L \in NP$ називається повним, якщо для всіх предикатів з класу NP зводиться до цього предикату за поліноміальний час

Предикат SAT. Теорема Кука

Теорема Кука

$SAT(x)= \begin{cases} 1\\ 0 \end{cases}$

1 - виконлива формула
0, тотожно-хибна

На вхід: формула числення висловлювань ${\lnot, \land, \lor}$ (код формули) ((1,1) (1,0), (0,1))

SAT є NP-повним предикатом

Доведення:

1) $SAT \in NP$ Інтерпритацію висловлювань пред'явити, де формула єв виконливою

Головна (*,*) - головна, (коди підформул)(коди підформулу)(бінарне дерево)

2) $SAT \in$ NP-повна

$L(x) \in NP$ , зведемо його до SAT,R - визначено через MT

$x_n y_1 \dots y_j$
$z_1, \dots x_n$
$x i y j$ - вхідні дані
x- зафіксовано
Z=Z(x,y)
кожна комірка має бути узгоджена з 3ма верхніми
q_i-стан керуючого пристрою
x₁ = *, q_j (двійковий код)

Підставимо в x конкретні значення

Треба побудувати по цій машині формулу числення висловлювань.

Z=Z(x,y)-додаткові дані $φ x (y, z)$ - ми використовуємо при керувані змінних

умова узгодженості $\underset{\Lambda}{t,s}\phi_{\overset{t,s}{x}}(y)$ Якщо формула виконлива, то прийдемо до 1 в кінці, інакше на якомусь кроці отримуємо неузгодженість

Виконлива означає, що $\exists y_i$ , що ми виходимо. Якщо $L \in$ NP-повними, то він зводиться до SAT

Означення

Предикат 3-SAT

3- КНФ

$(a^{\varepsilon} \lor b^{\varepsilon} \dots) \land$

КНФ називається 3-КНФ, якщо кожен диз'юнкт складається з 3ох доданків.

3-SAT = є шифр формули, яка записана у вигляді 3-КНФ

$L \in NP$ $L \varpropto SAT(x) \varpropto 3-SAT R(x,y) \in P$ : Нехай існує булева схема:

$y:=x_1 \lor x_2$
$y:=x_1 \land x_2$
$y:=\lnot x$

$y \leftrightarrow (x_1 \lor x_2) \simeq (y \to (x_1 \lor x_2))\land(x_1 \lor x_2 \to y)$

Потім беремо $\land$ всіх. Формула виконлива значить булева схема дасть 1

$2-SAT \in P$

Приклади рiзних NP− повних проблем, що отримуються через полiномiальну звiднiсть

Цілочисельне лінійне програмування (JLP)

$3-SAT \varpropto JLP$ $\sum_{j=1}^m u_j x_j \ge b_i$

$u_j \in Z$
$b_i \in Z$

$JLP(x)=1 \Leftrightarrow \exists solving \in Z$

$x \rightsquigarrow x$ (перетворює x з булевою змінної на цілочисельну)

$\lnot x \rightsquigarrow 1-x$

$u_1 \lor u_2 \lor u_3 \rightsquigarrow u_1 + u_2 + u_3$

$\begin{cases} \\u_1+u_2+u_3 \ge 1 0 \le x_i \le 1 \end{cases}$

Ймовiрноснi алгоритми, клас предикатiв BPP, машинне та предикатне означення

BPP (Beunded Polynomial Probability)

Означення 1 PMT - probability MT Предикат $L \in BPP$ якщо існує поліном p(n): машина зупиниться через час p(|x|) кроків

Якщо L(x)=1, то машина M зупиниться і дасть відповідь "так"

$L(x)=0 \Rightarrow$ (M з ймовірністю > 2/3 дає відповідь з ймовірністю > 2/3 так ) відповідь ні

Означення 2 $L \in BPP$ , якщо існує поліном $q(n) i R(\cdot , \cdot) \in P$ доля слів y завдовжки |y|=q(|x|), $L(x)=1 \rightarrow$ таких що $R(x,y)=1: > \frac{2}{3}$

|y|=q(|x|), $L(x)=0 \rightarrow R(x,y)=0: >\frac{2}{3}$

${ (x,y | R(x,y) \land (|y|=q(|x|)) }$

Ймовiрносний алгоритм перевiрки простоти числка. Довести, що вiн належить класу BPP

Теорема

Якщо n- просте, то P-M- алгоритм з ймовірністю 1 дає правильну відповідь, якщо ж n- складене, то правильна відповідь буде отримана з ймовірністю ≥ 1/2. Можна застосувати кілька разів і отримати помилку < $< \frac{1}{2^n}$

Доведення

1)

n 1, n 2

x=a₁ mod n₁
x=a₂ mod n₂
НСД (n₁, n₂)

При будь-якому a₁, a₂ розв'язок існує і єдиний x за mod n₁ n₂

2) $Z_{n_1 n_2} \simeq Z_{n_1} \bigoplus Z_{n_2}$ (ізоморфізм ділення)

Ізоморфізм - це бієкція узгоджена з операціями

китайська теорема про лишки

Довести включення BPP ⊂ P/poly

$BPP \subset P/poly$ Доведення

$\varepsilon$ -ймовірність помилки $L(x) \sim R(x,y) \in P$

Якщо L(x)=1 то доля y, для яких R(x,y)=0 менша за $\varepsilon$

$X \to Y_x$ - множина Y які для заданого x шукають правильну відповідь

$Y_x \subset 2^{q(|x|)}$ - множина булевих векторів розміру q(|x|)

$\bar{Y_x}$ - дають неправильну відповідь

$\varepsilon \cdot 2^{|x|}<1$ - зробити багатократним повторенням, дає помилку < 1

$\frac{\bar{Y_x}}{2^{q(|x|)}} \cdot 2^{|x|}<1$

$|\bar{Y_x}| \cdot 2^{|x|} < 2^{q(|x|)}$

$|\underset{x:x=|x|}{\cup \bar{Y_x}}| \le \sum_x |\bar{Y_x}|$ Не можна покрити $\bar{Y}_x$ всю множину - значить існує Y-універсальна яка кожного x заданої множини дає правильну відповідь.