APX Твердость подразумевает отсутствие QPTAS?

Таким образом, быстрый поиск в сети привел меня к мысли, что «APXHardness подразумевает, что для проблемы не существует QPTAS, если [некоторый класс сложности] не включен в некоторый [другой класс сложности]», и это тоже хорошо известно! Кажется, все это знают, кроме меня. К сожалению, нет никаких ссылок в поддержку этого утверждения. У меня есть два вопроса:

Какая самая сильная версия этого утверждения известна в настоящее время?
Ссылка? Пожалуйста?

Заранее спасибо.

Ответ Чандры Чекури предполагает, что для трудной проблемы подразумевает . Может кто-нибудь объяснить, почему это так, или желательно дать ссылку на это? Другими словами, почему квазиполиномиальная временная аппроксимация подразумевает QP-временную разрешимость? $QPTAS$ $APX$ $NP\subseteq QP$

cc.complexity-theory reference-request Сариэль Хар-Пелед
источник

Ответы на этот вопрос: cstheory.stackexchange.com/questions/9350/… показывают, что крайне маловероятно, что MAX 3SAT допускает что-либо лучше, чем 7/8 в субэкспоненциальное время (вряд ли обусловлено ETH).

Суреш Венкат

APX-Hardness подразумевает, что существует такое, что задача не допускает -аппроксимации, если . Очевидно, что это исключает PTAS (при условии, что ). Что касается QPTAS, он исключит это, если вы не уверены, что NP содержится в квазиполиномиальном времени. Насколько я знаю, это единственная причина, по которой APX-Hardness исключает QPTAS. $\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

Так как несколько человек спросили больше деталей, вот еще некоторые. APX-Hardness для задачи минимизации P подразумевает, что существует фиксированное и сокращение за полиномиальное время с 3-SAT до P, так что -приближение для P позволяет решить, является ли 3 -SAT формула выполнима или нет. Если существует QPTAS для P, мы можем получить для любой фиксированной a -аппроксимации во времени, скажем, . Но это подразумевает, что мы можем решить, выполнима ли формула 3-SAT за время, что, в свою очередь, означает, что NP находится в QP. $\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ $n^{O(\log n)}$

Чандра Чекури
источник

Почему (PTAS P = NP) означает (QPTAS )? Разве QPTAS не означает приближение в квазиполиномиальном времени, в то время как требует точного решения?

⟹

$\implies$

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

РБ

@chandra Да. Это правдоподобно, реф? (За исключением явного прохождения деталей твердости аппроксимации для 3SAT и т. Д., Что не сложно, но ссылка была бы лучше ...)

Сариэль Хар-Пелед

@ChandraChekuri Я почти наверняка буду плотным здесь, но если ваш QPTAS для 3SAT запустился вовремя , то я не вижу, как я могу сделать вывод, что Я бы выбрал 3SAT во время QP (потому что, вероятно, мне нужно было бы установить . Если не произойдет какого-либо усиления, которое я пропускаю.

n^{O (\log n)} 2^{1 / δ}

$n^{O(\log n)}2^{1/\delta}$

δ = 1 / n

$\delta = 1/n$

Суреш Венкат

@SureshVenkat Вам нужно использовать теорему PCP, которая гласит, что лучше, чем приближение 7S8 к 3SAT, - это NPHard. Вот почему я хочу реф;).

Сариэль Хар-Пелед

@SureshVenkat QPTAS не для 3-SAT. Именно для задачи P и является фиксированной константой. APX-Hardness для P подразумевает, что существует фиксированная константа , так что любой алгоритм, который решает лучше чем -solves 3-SAT. Зависимость времени работы QPTAS для от может быть произвольно плохой, но я собираюсь использовать его только для которая исправлена.

δ

$\delta$

δ

$\delta$

P

$P$

(1 + δ)

$(1+\delta)$

P

$P$

ϵ

$\epsilon$

ϵ = δ

$\epsilon = \delta$

Чандра Чекури

APX Твердость подразумевает отсутствие QPTAS?

Ответы: