Существуют ли известные естественные примеры задач оптимизации, для которых гораздо проще найти оптимальное решение, чем оценить качество данного варианта решения?
Для конкретности мы можем рассмотреть задачи оптимизации, решаемые за полиномиальное время, в форме: «заданный x, минимизируйте », где f : { 0 , 1 } ∗ × { 0 , 1 } ∗ → N скажем, # P-hard. Такие проблемы явно существуют (например, мы могли бы иметь f ( x , 0 ) = 0 для всех x, даже если f не вычислима), но я ищу «естественные» проблемы, демонстрирующие это явление.
Вот пример, где можно получить решение за полиномиальное время, но оценка данного решения является NP- трудной.
Примечание. Если мы хотим только проверить, является ли решение оптимальным , то это легко, поскольку известно, что граф Турана является единственным оптимальным, поэтому достаточно сравнить граф-кандидат с графом Турана, который имеет простую структуру , С другой стороны, если мы хотим оценить качество возможного решения, как того требует вопрос, а именно, возможно ли оно и насколько оно далеко от оптимального, то мы должны проверить, удовлетворяет ли оно максимальной клике. ограничение.
источник