Два общих предположения для доказательства твердости результатов аппроксимации - это и гипотеза об уникальных играх. Есть ли какая-либо сложность результатов аппроксимации, предполагающих ? Я ищу проблему такую, что «трудно приблизить пределах коэффициента если ».N P ≠ c o N P A A α N P = c o N P
Известно, что «показ фактор NP-твердости для кратчайшей векторной задачи будет означать, что ». Обратите внимание, что это «противоположность» тому, что я ищу.N P = c o N P
Пояснение: возможно, что и все же вопрос P против NP остается открытым. Я ищу результат приближения твердости, который станет ложным, если но не затронут (то есть, все еще остается в качестве предположения) .N P = C O N P P ≠ N P
approximation-hardness
conditional-results
Шива Кинтали
источник
источник
Ответы:
Вот прямое наблюдение. Если предположить , , то это довольно легко видеть , что есть N P проблемы оптимизации , которые даже не имеют хорошие недетерминированные алгоритмы аппроксимации, в некотором смысле.Nп≠ c o Nп Nп
Например, теорема PCP говорит, что вы можете перевести SAT в задачу определения того , удовлетворяются ли предложений и выполнены ли все предложения для некоторого ε > 0 . Предположим, что существует недетерминированный алгоритм, который может различать эти два случая, в том смысле, что недетерминированный алгоритм может сообщать на каждом пути вычислений либо «все выполнено», либо «не более 1 - ε », и он говорит «не более 1 - ε». "в некотором пути, если не более 1 - ε1 - ε ε > 0 1 - ε 1 - ε 1 - ε может быть удовлетворено, в противном случае он говорит «все удовлетворены» на каждом пути вычисления, если все уравнения могут быть выполнены. Этого достаточно , чтобы решить SAT в , так N P = C O N P . Очевидно , что наличие такого недетерминированного алгоритма не имеет никакого отношения ли P = N P .c o Nп Nп= с о нп п= Nп
Вполне вероятно , что более «естественный» сценарий существует: задача оптимизации , которую трудно аппроксимировать в детерминированной полиномиальное время при , но не известно , что будет трудно при P ≠ N P . (Это, вероятно, то, что вы действительно хотели спросить.) Многие результаты аппроксимации твердости сначала доказываются при более строгом предположении (например, N P не в субэкспоненциальном времени или N P не в B P P ). В некоторых случаях последующие улучшения ослабляют необходимое предположение, иногда вплоть до P ≠ NNп≠ c o Nп п≠ Nп Nп Nп Б Пп . Таким образом, есть надежда, что есть несколько более удовлетворительный ответ на ваш вопрос, чем этот. Трудно удивлениикак может быть проблемакотораяне можетбыть доказана трудно аппроксимировать в детерминированной полиномиальныхпри P ≠ N P , но этоможетбыть доказанотрудно под N P ≠ с O N P . Это означало бы, что N P ≠ c o N P говорит нам кое-что о детерминированных вычислениях, которые P ≠ N P еще не говорит; Интуитивно это трудно понять.п≠ Nп п≠ Nп Nп≠ c o Nп Nп≠ c o Nп п≠ Nп
источник
Отказ от ответственности: это не прямой ответ.
На самом деле существует гораздо больше условий твердости, кроме P! = NP и UGC. Дэвид Джонсон написал прекрасную колонку для транзакций по алгоритмам еще в 2006 году именно по этому вопросу. Он перечисляет многочисленные различные предположения, которые используются, чтобы показать твердость, и как они связаны друг с другом.
К сожалению, это все NP против детерминированных классов (за исключением NP и co-AM). NP против co-NP не покрывается вообще.
источник
источник
Это не прямой ответ
Нога Алон, Ограниченные раскраски графиков
источник