lower-bounds.tex

\chapter{Долни граници}

\section{Какво са долни граници?}

Дойде времето за по-депресиращите резултати в курса.
До сега единственото, което правихме, беше да показваме, че за задача $\mathbf{X}$ може да се напише алгоритъм със времева сложност $O(f)$ или $\Theta(f)$ за някое $f \in \mathcal{F}$.
Доста естествено изниква следния въпрос:
\begin{center}
    \textit{Възможно ли е да съществува по-бърз алгоритъм, който решава задачата $\mathbf{X}$?}
\end{center}
Ясно е, че е неприемлив отговор от сорта на
\begin{center}
    \textit{Не мога да измисля такъв алгоритъм, следователно такъв алгоритъм не съществува.}
\end{center}
В тази тема ще се опитаме да отговорим в някакъв смисъл положително на въпроси от този тип.
Преди това нека въведем няколко дефиниции.

\textbf{Изчислителна задача} ще наричаме всяко множество от наредени двойки $\mathbf{X}$, като:
\begin{itemize}
    \item $\operatorname{Dom}(\mathbf{X})$ ще наричаме \textbf{вход};
    \item $\operatorname{Rng}(\mathbf{X})$ ще наричаме \textbf{изход}.
\end{itemize}
За пример можем да вземем изчислителната задача \textbf{Sort}:

\vspace*{2mm}
\textbf{Вход:} Целочислен масив $A[1 \dots n]$.

\textbf{Изход:} Пермутация $A'[1 \dots n]$ на $A[1 \dots n]$, за която $A'[1] \leq A'[2] \leq \dots \leq A'[n]$.
\vspace*{2mm}

\newpage

Ще казваме, че \textbf{алгоритъм} $\mathbf{AlgX}$ \textbf{решава задачата} $\mathbf{X}$, ако за всяко $x \in \operatorname{Dom}(\mathbf{X})$ е изпълнено $\opair{x, \mathbf{AlgX}(x)} \in \mathbf{X}$.
Нека $\mathbf{X}$ е изчислителна задача и нека $f \in F$.
Тогава:
\begin{itemize}
    \item Казваме, че $f$ е \textbf{долна граница} за $\mathbf{X}$, ако всеки алгоритъм, който решава $\mathbf{X}$, работи за време (или брой операции от конкретен вид) поне $f$\footnote{
              Тук се има предвид, че ако $T(n)$ е броят на стъпки (или операции от конкретен вид), за който алгоритъма завършва при вход с големина $n$, то $f(n) \leq T(n)$.
          }.
    \item Казваме, че $\Omega(f)$ е \textbf{долна граница} за $\mathbf{X}$, ако всеки алгоритъм, който решава $\mathbf{X}$, работи за време (или брой операции от конкретен вид) $\Omega(f)$.
\end{itemize}
\section{Техники за изследване на долни граници}

Най-често се използват следните техники, които показват че задача $\mathbf{X}$ има долна граница за време $f$ (или $\Omega(f)$):
\begin{itemize}
    \item директни разсъждения за конкретния пример -- тази техника обикновено се използва в малки задачи, където човек за сравнително малко време може да направи пълен анализ.
          Разбира се, тази техника се използва и при по-обобщените примери, но не толкова често.
    \item дърво на взимане на решения -- тази техника се използва в задачи, където за решаването им се изисква задаването на редица въпроси, чиите отговор ни дава все повече и повече информация.
          Можем да си мислим за запитванията заедно с информацията, която носят, като едно дърво.
          Всеки въпрос ще разклонява дървото, докато накрая имаме цялата ни нужна информация в листата, и не трябва да задаваме повече въпроси.
          Тогава долната граница ще бъде височината на дървото.
    \item аргументация чрез противник -- тази техника е трудна да се обясни без да се даде пример.
          Идеята е, че играем срещу противник, като нашата цел е да разкрием някаква информация, която уж е била предварително фиксирана.
          Противника обаче си измисля информацията на момента, като целта му е да ни накара да зададем колкото се може повече въпроси и в отговорите му на въпросите да няма противоречия.
    \item чрез редукция\footnote{
              Това е може би най-приложимата техника от всички.
              Тя се използва не само в контекста на сложност.
              Оказва се, че е много удобно човек да може да говори за това дали една задача е \textit{``по-трудна''} от друга в контекста на разрешимост.
          } -- ако знаем, че можем алгоритмично да сведем задача $\mathbf{Y}$ до задача $\mathbf{X}$ за време $o(f)$ и $\mathbf{Y}$ има долна граница за време (или брой операции от конкретен вид) $\Omega(f)$, то тогава второто е изпълнено и за задача $\mathbf{X}$.
          В някакъв смисъл тази редукция казва, че задачата $\mathbf{X}$ е поне толкова трудна, колкото задачата $\mathbf{Y}$.
\end{itemize}

\section{Техниките в действие}

Ще започнем със пример за аргументация с противник.
Решаваме задачата за максимален елемент -- даден ни е като вход целочислен масив $A[1 \dots n]$ и искаме да получим като изход $\max \{ A[i] \mid 1 \leq i \leq n \}$.
Твърдим, че всеки алгоритъм, който решава задачата, използва поне $n - 1$ сравнения.
Ако при работа на алгоритъма е проверено условието ``$A[i] \leq A[j]$'' и е върнало $\T$, ще казваме, че $A[i]$ е загубило това сравнение и $A[j]$ е спечелило това сравнение.
Нека $A[i]$ е максималният елемент на $A[1 \dots n]$.
Тогава за всяко $j \neq i$ имаме, че $A[j]$ е загубило сравнение.
Ако има $A[j]$, което не е загубило сравнение, то тогава $A[j]$ не е сравнявано с $A[i]$.
Ако сменим $A[j]$ със $A[i] + 1$, то тогава при изпълнението на алгоритъма резултатите (от сравненията) няма да се променят, и алгоритъмът ще върне $A[i]$, което е абсурд.
Тъй като при всяко сравнение един връх печели, а другия губи, то за да постигнем тези $n - 1$ загуби ни трябват $n - 1$ сравнения.
Ако си представим какво прави стандартния алгоритъм за намиране на максимум, той постоянно поддържа победител.
Започва с един елемент, и когато той загуби, го заменя с друг.
Накрая ще сме завършили с елемент, който никога не е губил, и е транзитивно е победил всички останали.

Нека сега дадем пример за дърво на вземане на решения.
Разглеждаме задачата \textbf{Sort}.
Ще покажем, че всеки сортиращ алгоритъм, който работи на базата на директни сравнения, работи за време $\Omega(n \log (n))$.
Нека фиксираме $n \in \N$ и някакъв символ $a$.
Нека $\calT_n$ е множеството от всички дървета, за които е изпълнено, че:
\begin{itemize}
    \item върховете са от вида $(a_i < a_j, P)$, където $1 \leq i, j \leq n, \; P \subseteq S_n$\footnote{$S_n$ е симетричната група за $\{ 1, \dots, n \}$.} и $|P| \geq 2$, или са от вида $\sigma \in S_n$;
    \item ако $n > 1$, то коренът е $(a_i < a_j, S_n)$ за някои $1 \leq i, j \leq n$, иначе е единственият елемент на $S_n$;
    \item за всеки връх от вида $(a_i < a_j, P)$, има $1 \leq k_1, k_2, m_1, m_2 \leq n$, за които:
          \begin{itemize}
              \item лявото му дете (стига да е добре дефинирано т.е. дясната компонента не е $\varnothing$) е наредената двойка $(a_{k_1} < a_{m_1}, \{ \sigma \in P \mid \sigma(i) < \sigma(j) \})$ (или ако се получава само една пермутация, само тя), и
              \item дясното му дете (стига да е добре дефинирано т.е. дясната компонента не е $\varnothing$) е наредената двойка $(a_{k_2} < a_{m_2}, \{ \sigma \in P \mid \sigma(i) \not< \sigma(j) \})$ (или ако се получава само една пермутация, само тя).
          \end{itemize}
\end{itemize}
Тогава ако вземем произволен алгоритъм за сортиране $\mathbf{AlgX}$, който е базиран на сравнение, при пресмятането на $\mathbf{AlgX}(A[1 \dots n])$, можем да забележим, че траверсираме някое дърво $T \in \calT_n$ от корен до листо.
В корена се намира първото запитване $a_i < a_j$ (т.е. можем да си мислим, че питаме дали $A[i] < A[j]$, където $A[i], A[j]$ са първоначалните стойности на входния масив), и спрямо отговора на дадено запитване ние се движим наляво или надясно в дървото.
Накрая се намираме в листо $\sigma \in S_n$, която задава сортирана пермутация $A'[1 \dots n]$ на $A[1 \dots n]$ така -- $A'[i] = A[\sigma(i)]$.
Това означава, че за всяко сравнение по време на работа на $\mathbf{AlgX}(A[1 \dots n])$ можем да си мислим, че минаваме през едно ребро в $T$.
В най-лошия случай входът $A[1 \dots n]$ би бил такъв, че да трябва да изминем максимален път от корен до листо т.е. път с дължина $h(T)$ (височината на дървото).
Но $T$ е двоично дърво с $n!$ листа и разклоненост $2$, следователно $h(T) \geq \log_2(n!)$.
Така в този случай извикването $\mathbf{AlgX}(A[1 \dots n])$ ще използва поне $\log(n!)$ сравнения.
Тъй като $\log(n!) \asymp n \log(n)$, получаваме че всеки сортиращ алгоритъм, базиран на сравнения, прави $\Omega(n \log(n))$ сравнения.
Нещо повече, това ще е вярно и за масив от естествени числа.
Тук никъде не се възползваме от това, че числата са цели.
Възползвахме се от това, че са безкрайно много.

Нека сега покажем един пример с редукция.
Разглеждаме изчислителната задача \textbf{Матрьошки}:

\textbf{Вход:} Масив $T[1 \dots n]$ със елементи от вида $(l, w, h)$ -- дължините, широчините, височините на $n$ играчки с форма на правоъгълен паралелепипед, които могат да се вложат една в друга.

\textbf{Изход:} Ред на влагане на играчките, като вътрешната играчка е първа.

Оказва се, че тази задача се решава (на базата на директни сравнения) за време $\Omega(n \log(n))$.
Ще покажем това като сведем задачата за сортиране на естествени числа към \textbf{Матрьошки}.
Нека $\mathbf{AlgM}$ е алгоритъм, който решава задачата \textbf{Матрьошки} със сложност по време $f(n)$.

\newpage

Тогава следният алгоритъм очевидно сортира масива от естествени числа $A[1 \dots n]$:
\begin{enumerate}
    \item Декларираме нов масив $T[1 \dots n]$.
    \item За всяко $1 \leq i \leq n$ инициализираме $T[i]$ със $(A[i], A[i], A[i])$.
    \item Извикваме $\mathbf{AlgM}(T[1 \dots n])$ с резултат $T'[1 \dots n]$.
    \item Декларираме нов масив $A'[1 \dots n]$
    \item За всяко $1 \leq i \leq n$ инициализираме $A'[i]$ със най-лявата компонента на $T'[i]$.
    \item Връщаме $A'[1 \dots n]$.
\end{enumerate}
Сложността на алгоритъма е $\Theta(n + f(n))$.
Ако $f(n) = o(n \log(n))$, щяхме да получим сортиращ алгоритъм, който работи за време $o(n \log(n))$, което е абсурд.

\section{Задачи}

\begin{problem}
Един целочислен масив $A[1 \dots 2n]$ ще наричаме симетричен, ако за всяко $1 \leq i \leq n$ е изпълнено, че $A[i] = A[2n - i + 1]$.
Да се докаже, че сортирането на симетрични масиви чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Един целочислен масив $A[1 \dots 2n]$ ще наричаме специален, ако за всяко $1 \leq i \leq n$ е изпълнено, че $A[2i] < A[2i - 1]$.
Да се докаже, че сортирането на специални масиви чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Разглеждаме задачата \textbf{SortPointsCounterClockwise}:

\vspace*{2mm}
\textbf{Вход:} Точки $P_1, \dots, P_n \in \N \cross \N$.

\textbf{Изход:} Последователност $P'_1, \dots, P'_n$ на точките $P_1, \dots, P_n$, за която за всяко $1 \leq i < n$ е изпълнено, че най-малкото завъртане от вектора $\overrightarrow{OP'_i}$ към вектора $\overrightarrow{OP'_{i + 1}}$ става обратно на часовниковата стрелка, където $O$ е началото на координатната система.
\vspace*{2mm}

Да се докаже, че решението на задачата \textbf{SortPointsCounterClockwise} чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\newpage

\begin{problem}
Разглеждаме задачата \textbf{SortPointsAngle}:

\vspace*{2mm}
\textbf{Вход:} Точки $P_1, \dots, P_n \in \N \cross \N$.

\textbf{Изход:} Подреждане на точките $P_1, \dots, P_n$ по големина на ъгъла, който сключва радиус-векторът с $Ox$.
\vspace*{2mm}

Да се докаже, че решението на задачата \textbf{SortPointsAngle} чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Нека $A[1 \dots n]$ и $B[1 \dots n]$ са сортирани целочислени масиви.
Да се докаже, че $2n - 1$ е долна граница за броя на сравнения при сливането на тези два масива в един сортиран масив $C[1 \dots 2n]$.
\end{problem}

\begin{problem}
Даден е граф с $2n$ върха.
Интересуват ни въпроси от вида:
\begin{center}
    \textit{``Има ли ребро от връх} $i$ \textit{до връх} $j$\textit{?''}
\end{center}
Да се докаже, че $n^2$ е долна граница за броя въпроси, който е нужен, за да установим дали дадения граф е свързан.
\end{problem}

\begin{problem}
Искаме да познаем число между $1$ и $n$, което някой друг човек е намислил.
За целта можем да му задаваме въпроси (на които той трябва да отговори честно) от вида:
\begin{center}
    \textit{``Вярно ли е, че} $k$ \textit{е по-малко от намисленото число?''}
\end{center}
Да се докаже, че $\lceil \log_2(n) \rceil$ е долна граница за броя въпроси, който е нужен, да познаем намисленото число.
\end{problem}

\begin{problem}
Да се докаже, че сортирането на двоична пирамида чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Дефинираме вълнист масив индуктивно:
\begin{itemize}
    \item Всеки едноелементен масив е вълнист.
    \item Масив $A[1 \dots n]$ (където $n > 1$) е вълнист, ако
          \begin{enumerate}
              \item масивът $A[1 \dots \lfloor \frac{n}{2} \rfloor]$ е сортиран, а
              \item масивът $A[\lfloor \frac{n}{2} \rfloor + 1 \dots n]$ е вълнист.
          \end{enumerate}
\end{itemize}
Да се докаже, че пермутирането на масив до вълнист изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Да се докаже, че строенето на двоична пирамида от масив $A[1 \dots n]$ изисква $n - 1$ сравнения.
\end{problem}

\begin{problem}
Разглеждаме задачата \textbf{ElementUniqueness}:

\vspace*{2mm}
\textbf{Вход:} Целочислен масив $A[1 \dots n]$.

\textbf{Въпрос:} Вярно ли е, че масивът $A[1 \dots n]$ съдържа само уникални елементи?
\vspace*{2mm}

Да се докаже, че решението на задачата \textbf{ElementUniqueness} чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Разглеждаме задачата \textbf{Mode}:

\vspace*{2mm}
\textbf{Вход:} Целочислен масив $A[1 \dots n]$.

\textbf{Изход:} Най-често срещано число в $A[1 \dots n]$.
\vspace*{2mm}

Да се докаже, че решението на задачата \textbf{Mode} чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}

\begin{problem}
Разглеждаме задачата \textbf{ClosestPair}:

\vspace*{2mm}
\textbf{Вход:} Целочислен масив $A[1 \dots n]$.

\textbf{Изход:} $\min \{ |A[i] - A[j]| \mid 1 \leq i < j \leq n \}$.
\vspace*{2mm}

Да се докаже, че решението на задачата \textbf{ClosestPair} чрез сравнения изисква време $\Omega(n \log(n))$.
\end{problem}