Проблемы оптимизации NP (определение)

Question

Я пытаюсь понять определение НКО.

Я прочитал определение здесь: http://www.nada.kth.se/~viggo/wwwcompendium/node2.html

Если мы рассмотрим попытку найти минимальное покрытие вершин, что такое I, sol (x) и m? (цель мин)

Answer 1

Судя по ссылке, которую вы разместили, я думаю, что это интерпретация для минимального покрытия вершин :

• I : набор всех графиков.
• sol (x) : Множество возможных решений графа x ∈ I , то есть все подмножества вершин, которые покрывают все ребра.
• m (x, y) : значение решения y для экземпляра x . В случае покрытия вершин количество вершин в наборе.