Твердость аппроксимации при условии NP! = CoNP

32

Два общих предположения для доказательства твердости результатов аппроксимации - это и гипотеза об уникальных играх. Есть ли какая-либо сложность результатов аппроксимации, предполагающих ? Я ищу проблему такую, что «трудно приблизить пределах коэффициента если ».N P c o N P A A α N P = c o N PPNPNPcoNPAAαNP=coNP

Известно, что «показ фактор NP-твердости для кратчайшей векторной задачи будет означать, что ». Обратите внимание, что это «противоположность» тому, что я ищу.N P = c o N PnNP=coNP

Пояснение: возможно, что и все же вопрос P против NP остается открытым. Я ищу результат приближения твердости, который станет ложным, если но не затронут (то есть, все еще остается в качестве предположения) .N P = C O N P P N PNP=coNPNP=coNPPNP

Шива Кинтали
источник
@ Kintali, Результат СВП интересный. Известны ли вам другие примеры, похожие на кратчайший вектор проблемы?
Мухаммед Аль-Туркистани
Я не знаю больше таких результатов.
Шива Кинтали

Ответы:

20

Вот прямое наблюдение. Если предположить , , то это довольно легко видеть , что есть N P проблемы оптимизации , которые даже не имеют хорошие недетерминированные алгоритмы аппроксимации, в некотором смысле.NPcoNPNP

Например, теорема PCP говорит, что вы можете перевести SAT в задачу определения того , удовлетворяются ли предложений и выполнены ли все предложения для некоторого ε > 0 . Предположим, что существует недетерминированный алгоритм, который может различать эти два случая, в том смысле, что недетерминированный алгоритм может сообщать на каждом пути вычислений либо «все выполнено», либо «не более 1 - ε », и он говорит «не более 1 - ε». "в некотором пути, если не более 1 - ε1εε>01ε1ε1εможет быть удовлетворено, в противном случае он говорит «все удовлетворены» на каждом пути вычисления, если все уравнения могут быть выполнены. Этого достаточно , чтобы решить SAT в , так N P = C O N P . Очевидно , что наличие такого недетерминированного алгоритма не имеет никакого отношения ли P = N P .coNPNP=coNPP=NP

Вполне вероятно , что более «естественный» сценарий существует: задача оптимизации , которую трудно аппроксимировать в детерминированной полиномиальное время при , но не известно , что будет трудно при P N P . (Это, вероятно, то, что вы действительно хотели спросить.) Многие результаты аппроксимации твердости сначала доказываются при более строгом предположении (например, N P не в субэкспоненциальном времени или N P не в B P P ). В некоторых случаях последующие улучшения ослабляют необходимое предположение, иногда вплоть до P NNPcoNPPNPNPNPBPP . Таким образом, есть надежда, что есть несколько более удовлетворительный ответ на ваш вопрос, чем этот. Трудно удивлениикак может быть проблемакотораяне можетбыть доказана трудно аппроксимировать в детерминированной полиномиальныхпри P N P , но этоможетбыть доказанотрудно под N P с O N P . Это означало бы, что N P c o N P говорит нам кое-что о детерминированных вычислениях, которые P N P еще не говорит; Интуитивно это трудно понять.PNPPNPNPcoNPNPcoNPPNP

Райан Уильямс
источник
Да. Трудно понять, что такие результаты твердости даже возможны. Мне было интересно, можем ли мы доказать несуществование таких результатов твердости. Фу .... это становится сложным.
Шива Кинтали
(1) Я боюсь, что во втором абзаце вы пишете «да» и «нет» противоположно. Легко построить недетерминированный алгоритм, который делает то, что вы заявили (сообщает «все удовлетворены» хотя бы в одном пути, если формула выполнима, и сообщает «не более 1-ε» во всех путях, если формула ε-далека от выполнимой просто проверяя все назначения правды недетерминированно. (2) Я согласен с тем, что трудно понять.
Цуёси Ито
8

Отказ от ответственности: это не прямой ответ.

На самом деле существует гораздо больше условий твердости, кроме P! = NP и UGC. Дэвид Джонсон написал прекрасную колонку для транзакций по алгоритмам еще в 2006 году именно по этому вопросу. Он перечисляет многочисленные различные предположения, которые используются, чтобы показать твердость, и как они связаны друг с другом.

К сожалению, это все NP против детерминированных классов (за исключением NP и co-AM). NP против co-NP не покрывается вообще.

Суреш Венкат
источник
2
Как интересно, Дэвид Джонсон рассказывает о NP против co-NP в следующем столбце - столбец NP-полноты № 26 !
Даниэль Апон 20.10.10
ну конечно. Я должен был вспомнить. Но никаких приближений, хотя ...
Суреш Венкат
4

NPcoNPPNPNPcoNPPNPPNPNPcoNP

Мухаммед Аль-Туркистани
источник
3
Вполне возможно, что NP = coNP и все же P против NP вопрос открыт. Я ищу результат приближения твердости, который станет ложным, если NP = coNP, но не затронут (то есть, все еще остается в качестве предположения) P! = NP.
Шива Кинтали
AαNPcoNPα