\begin{document}

\maketitle

\section{}

Разделим наше множество на 2 подмножетсва по \(\frac{l}{2}\) в каждом (за \(O(l)\)). Для каждого подмножества подсчитаем все возможные суммы в нём (за \(2 * 2^{\frac{l}{2}} * O(\frac{l}{2}) = 2^{\frac{l}{2}} * O(l) \). Каждый список отсортируем за \(O(N * \log{N}) = 2 * O(2^{\frac{l}{2}} * \log 2^{\frac{l}{2}}) = 2^{\frac{l}{2}} * O(l)\). Будем двигаться по первому списку в порядке убывания, по второму в порядке возрастания. Если сумма текущих двух элементов больше \textbf{t},то надо уменьшить сумму, т.е. берём следующий элемент из первого списка, иначе берём следующий из второго (не более чем \(2 * 2^{\frac{l}{2}}\) шагов). Докажем,что алгоритм выдаёт правильный ответ. Если такого подмножества нет,то ни для одной пары сумма не сможет стать \textbf{t}. Значит,ответ нет. Если такое подмножество есть, то его сумма - это сумма его элементов из первого списка и второго списка. Значит, есть такие \textbf{a} и \textbf{b} в 1 и 2 списке,что a + b = t. Если мы находимся сейчас в \textbf{a} в нашем алгоритме,то все числа ,которые до \textbf{b} дают в сумме меньше \textbf{t},значит мы берем следующий элемент и так до тех пор пока не дойдём до \textbf{b}. Аналогично,если мы сейчас в \textbf{b}. Значит, алгоритм всегда даёт верный ответ. Время работы \(2^{\frac{l}{2}} * O(l)\).

\section{}

Запускаем два раза алгоритм A(G,k) - получаем результаты \(A_1, A_2\). Запускаем 2 раза алгоритм B(G,k) - получаем результаты \(B_1, B_2\). Пусть C = \((A_1 \vee B_1) \wedge (A_2 \vee B_2)\). Если есть клика,то \(A_1 = A_2 = 1\) => C = 1. Если есть независимое множество,то \(B_1 = B_2 = 1\) => C = 1. Если нет ни того,ни другого, то \(A_i = 0\) с вероятностью \(\geqslant \frac{1}{2}\), \( B_i = 0\) с вероятностью \( \geqslant \frac{1}{2}\) => \(A_i \vee B_i = 0\) с вероятностью \(\geqslant \frac{1}{4}\) => C = 0 с вероятностью \(\geqslant \frac{1}{4} + \frac{1}{4} = \frac{1}{2}\).

\section{}

Есть ли клика размера \textbf{k} - NP полная задача => Если предъявить для неё полиномиальный алгоритм ,это это будет значить,что P = NP. Алгоритм из задачи совершает \(\leqslant \log_2 n\) равновероятных выборов => всего различный последовательностей шагов \(\leqslant n\). Результаты их работы - листья такого дерева.

\includegraphics[scale=0.5]{derevo.png}

Алгоритм отвечает правильно с вероятностью \(\geqslant \frac{2}{3}\) => хотя бы в \(\frac{2}{3}\) листьях записан правильный ответ. Каждая ветка дерева представляет собой полномиальный алгоритм с временем работы \textbf{t}.Тогда посчитаем значения во всех листьях. Для этого нужно перебрать \(\leqslant n\) алгоритмов с временем работы \textbf{t} => понадобится n * t времени - полином. Проходимся по всем ответам и выбираем тот,который встречался больше всех - он и будет верным.

\section{}

Если скобок с одной переменной больше 0.6 от всего количества,то делаем их истинными, иначе делаем рандомное означивание. Получается,что скобки, в которых у нас \(\geqslant 2\) переменных, истинны с вероятность \(\geqslant \frac{3}{4}\). посчитаем мат ожидание количества истинных скобок,при условии,что количество скобок с одной перменной меньше 0.6n

Ep = \(\frac{1}{2}\) * (n-q) + \(\frac{3}{4}\) * q = (где q - количество истинных скобок,в которой больше 1 переменной,причём q \(\geqslant\) 0.4n ) = \(\frac{n}{2} - \frac{q}{2} + \frac{3q}{4} = \frac{n}{2} + \frac{q}{4} \geqslant \frac{n}{2} + \frac{n}{10} = \frac{6n}{10}\). Значит, в среднем получается \(\frac{1}{2} * 0.6n + \frac{1}{2} * 0.6n = 0.6n\). Получается наш алгоритм делает в среднем не менее 0.6n скобок истиннными.

\section{}
Возьмём произвольное упорядочивание маркеров $m_1, m_2,..., m_n$, тогда вероятность того,что i-ое ограничение будет верным будет равно $\frac{2}{6}$( 2 варианта взаиморасположений из 3-ёх элементов удовлетворяет данному условию). Значит,мат.ожидание количество верных ограничений будет равно сумме мат ожиданий индикаторных величин ограничений,тобишь равно сумме вероятностей того,что ограничение будет верно, а это $t * \frac{1}{3} = \frac{t}{3}$. Соответсвенно наше мат. ожидание будет отличаться от оптимального решения не более чем в 3 раза,т.к. $>\frac{t}{3}$ мы сможем получить, а больше $>t$ уже нет.

\end{document}