Полиномиальные распознающие алгоритмы. Что мы называем языком. Класс \(\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.