Термин «проблема оптимизации NP-hard» кажется слишком широким, чтобы можно было найти удовлетворительный ответ.
Например, я не понимаю, что мешает решению проблем с оптимизацией NP-hard.проблемы - если учесть, скажем, проблему MAX-CNF-SAT с решениями, оцениваемыми как пол (k / N), где k - количество удовлетворенных предложений, а N - общее количество предложений в экземпляре (которое являетсявычисляется в полиномиальном времени), тогда любая оценка, которая дает 1 в этой формуле, должна удовлетворять всей формуле.Итак, давайте предположим, что мы максимизируем минимальное значение (k / N) и назовем это задачей оптимизации FLOOR-CNF-SAT:)
Это означает, что вы можете уменьшить TAUTOLOGY до указанной проблемы оптимизации - отрицать ввод и добавить любое решениекак S. Вы можете даже добавить фиктивную переменную, чтобы убедиться, что исходное решение получает 0 в задаче FLOOR-CNF-SAT.Отрицание является полиномиальным по времени.
Тогда, если решатель для предложенной проблемы считает S неоптимальным, должна быть определенная оценка, которая дает 1 в соответствии с нашей созданной функцией и, таким образом, удовлетворяет всей формуле - вв свою очередь, предоставляя оценку, которая не удовлетворяет первоначальному вкладу в TAUTOLOGY.
Путем небольшого мошенничества (используя искусственно созданную задачу оптимизации) мы установили проблему «является оптимальной» как со-NP-полную, так как TAUTOLOGY являетсяЛегко показать, что он является со-NP-полным.
По вашему собственному аргументу, проблема «оптимального» решения является со-NP-сложной, поскольку в качестве свидетеля вам нужно только лучшее решение - наберите S, наберитепосмотрите и сравните.
Я не очень хорошо себя чувствую в связи с этим сокращением, но не могу легко улучшить класс задач.Если вам требуется, чтобы были экземпляры с произвольно высокой оценкой, а не просто {0, 1}, я мог бы просто использовать N * floor (k / N).Улучшение класса могло бы заключаться в том, чтобы рассматривать проблему как задачу оптимизации NP-hard только в том случае, если для каждого K существует экземпляр, который имеет по крайней мере K решений, которые оцениваются по-разному.
Я думаю, что все еще могу обмануть мой путь:
Рассмотрим сокращение, которое добавляет N фиктивных переменных к входу TAUTOLOGY следующим образом:
d1 && d2 && d3 ... && dN && (S)
, где S - этоотрицательный вход.В качестве начальной оценки я выбираю d1, ..., dN = false, но в качестве оценки я даю функцию, которая возвращает 2N - 1, если все первые N предложений ложны, в противном случае возвращается число удовлетворенных предложений.Такая функция вернула бы только 2N, если бы все условия были удовлетворены, но могла бы легко иметь по крайней мере N различных значений.
Боюсь, что без каких-либо сложных условий регулярности для функции оценки это лучшее, что мы можем получить,если вы не считаете, что определение задачи NP-трудной оптимизации является «проблемой, для которой, учитывая возможное решение S, мы можем за полиномиальное время проверить, является ли S оптимальным», и в этом случае «оптимальным» является ясно P иэто совсем не весело: /