Полиномиальные распознающие алгоритмы. Что мы называем языком. Класс $\mathsf P$.

Задача с сертификатом, задача оптимизации. Пример: Knapsack (задача о рюкзаке). Как из неё получить задачу поиска (задачу с yes-сертификатом).

Класс $\mathsf{NP}$, кратко о классах $\mathsf{NPH}$ ($\mathsf{NP}$-трудных языков) и $\mathsf{NPC}$ ($\mathsf{NP}$-полных языков).

Вершинное покрытие (vertex cover): дан граф $G=(V,E)$ с весами вершин из $\mathbb Q_{\geqslant0}$. Найти наименьшее по весу вершинное покрытие: каждое ребро должно быть инцидентно хотя бы одной вершине из покрытия.

Невзвешенное вершинное покрытие (cardinality vertex cover): дан только граф, а веса вершин равны единице. 2-приближённое решение с нахождением неувеличиваемого паросочетания.

Покрытие множествами (set cover): дано множество $U$, $|U|=n$, даны множества $\mathcal S=\left{S_1,\ldots,S_k\right}$ с весами, найти множества минимального суммарного веса, объединение которых равно $U$. Пусть $f$ — максимальная встречаемость элемента, тогда vertex cover — $f$-приближение, $f=2$. У Vertex cover за полином ищется $f$-приближение (не было на лекции). Также ищется $\mathcal O(\log n)$-приближение: брать множество наименьшей остаточной удельной стоимости. Пример, на котором точна $\mathcal O(\log n)$-оценка.

$k$-центр ($k$-center): дан полный граф $G=(V,E)$ с весами рёбер из $\mathbb Q_{\geqslant0}$, назовём расстоянием от вершины до множества вершин вес наименьшего ребра из этой вершины в какую-то вершину множества. Найти минимальный $k$-центр — набор из $k$ вершин, минимизирующий максимальное по $v$ расстояние от вершины $v$ до этого набора.

Если $\mathsf P\ne\mathsf{NP}$, то у задачи о $k$-центре нет $f(n)$-приближения ни для какой вычислимой функции $f(n)$, так как к ней можно свести $\mathsf{NP}$-полную задачу Dominating set.