Сложность проверки решений проблем с NP-жесткой оптимизацией?

Существует много проблем оптимизации, которые, как известно, являются NP-жесткими, такими как проблема коммивояжера, MAX-SAT или поиск минимального хроматического числа графика. Учитывая такую проблему, мне любопытно сложность следующей проблемы:

Учитывая проблему NP-жесткой оптимизации и решение кандидата S, является ли S оптимальным решением проблемы?

Интуитивно, похоже, что это может быть непротиворечивым, поскольку легко опровергнуть ответ на проблему оптимизации, угадывая лучшее решение и используя его в качестве свидетеля, но я понятия не имею, как это показать. На самом деле, я действительно не знаю, как рассуждать о сложности этой проблемы.

Кто-нибудь знает о каких-либо хороших нижних границах сложности этой проблемы решения? Знать, было ли это совместным NP трудно, PSPACE-hard и т.д. Было бы действительно интересно.

Ответ 1

Термин "проблема оптимизации NP-жесткости" кажется слишком широким, чтобы найти удовлетворительный ответ.

Например, я не вижу, что исключает возможность решения проблем, связанных с NP-жесткой оптимизацией, - если вы считаете, что проблема 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-полной.

По собственному аргументу "оптимальная" проблема решения является непротиворечивой, поскольку в качестве свидетеля вам нужно только лучшее решение - оценка S, оценка свидетеля и сравнение.

Я не очень хорошо отношусь к этому сокращению, но я не могу легко улучшить класс проблем. Если вам потребуются экземпляры, которые оцениваются как произвольно высокие, а не только {0, 1}, я мог бы просто использовать N * floor (k/N). Улучшение класса может состоять только в том, чтобы рассматривать проблему как задачу NP-hard optim, если для каждого K существует экземпляр, который имеет по крайней мере K решений, которые все оценивают по-разному.

Думаю, я все еще могу обмануть это:

Рассмотрим сокращение, которое добавляет N фиктивных переменных к входу TAUTOLOGY следующим образом:

d1 && d2 && d3 ... && dN && (S)

где S - отрицательный вход. В качестве начальной оценки я выбираю d1,..., dN = false, но в качестве оценки я даю функцию, которая возвращает 2N - 1, если первые предложения N являются ложными, в противном случае он возвращает количество удовлетворенных предложений. Такая функция вернет только 2N, если все предложения будут выполнены, но могут легко иметь по крайней мере N различных значений.

Я боюсь, что без каких-либо сложных условий регулярности для функции подсчета это лучшее, что мы можем получить, если вы не считаете определение NP-жесткой задачи оптимизации "проблемой", для которой, учитывая решение кандидата S, мы можем в полиномиальное время проверить, является ли S оптимальным ', и в этом случае "оптимально" явно P, и это вообще не забавно:/

Ответ 2

NP-жесткая проблема "по крайней мере такая же сложная задача, как и самые сложные проблемы в NP".

Пример NP-жесткой проблемы: проблема с остановкой (может ли программа A остановить или нет?):)

Скажем, у вас есть решение кандидата: "нет, программа A не может остановиться". Мы знаем, что вы не можете проверить это - он неразрешимый.

Вы даже не можете проверить, "да, программа A останавливается" - потому что это может занять навсегда, поэтому оно также невозможно решить.

Ответ 3

Потому что S - решение кандидата; учитывая, что нет других S, в которых S может быть доказано, что он жаден или менее оптимален, чем любой другой S. Необходимо, чтобы S находилось в то время как оптимальное решение MOST для проблемы.