Twardość APX oznacza brak QPTAS?

Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że „APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie podano odniesienia do tego oświadczenia. Mam dwa pytania:

Jaka jest najsilniejsza wersja tego stwierdzenia, która jest obecnie znana?
Referencja? Proszę?

Z góry dziękuję.

Odpowiedź Chandra Chekuri sugeruje, że o -hard problemu oznacza . Czy ktoś może wyjaśnić, dlaczego jest to prawdą, a najlepiej podać odniesienie? Innymi słowy, dlaczego quasi-wielomianowa aproksymacja czasu implikuje wypłacalność QP? $QPTAS$ $APX$ $NP\subseteq QP$

cc.complexity-theory reference-request

— Sariel Har-Peled
źródło

Odpowiedzi na to pytanie: cstheory.stackexchange.com/questions/9350/… pokazują, że jest wysoce nieprawdopodobne, aby MAX 3SAT dopuszczał coś lepszego niż 7/8 w czasie podwykonawczym (mało prawdopodobne, by zależało to od ETH).

— Suresh Venkat

APX twardości oznacza, że istnieje , tak że problem ten nie dopuścić do -approximation chyba że . Wyraźnie wyklucza to PTAS (przy założeniu ). Jeśli chodzi o QPTAS, to wykluczy to, jeśli nie uwierzysz, że NP jest zawarty w quasi-wielomianowym czasie. O ile mi wiadomo, jest to jedyny powód, dla którego twardość APX wyklucza QPTAS. $\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

Ponieważ kilka osób zapytało o więcej szczegółów, oto kilka innych. Twardość APX dla problemu minimalizacji P implikuje, że istnieje stała i redukcja czasu wielomianowego od 3-SAT do P, tak że przybliżenie dla P pozwala zdecydować, czy 3-SAT formuła jest zadowalająca lub nie. Jeśli istnieje QPTAS dla P, możemy uzyskać dla dowolnej stałej aproksymacji a w czasie, powiedzmy . Ale to oznacza, że możemy zdecydować, czy formuła 3-SAT jest zadowalająca w $\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ czas, co z kolei oznacza, że NP jest w QP. $n^{O(\log n)}$

— Chandra Chekuri
źródło

Dlaczego (PTAS

⟹

$\implies$ P = NP) średnia (QPTAS

)? Czy QPTAS nie oznacza przybliżenia w czasie quasi-wielomianowym, podczas gdy

wymaga dokładnego rozwiązania?

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

— RB

@chandra Yeh. To wiarygodne, ref? (Z wyjątkiem wyraźnego przejścia przez szczegóły twardości aproksymacji dla 3SAT i tak dalej, co nie jest trudne, ale ref byłoby lepsze ...)

— Sariel Har-Peled

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

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

δ = 1 / n

$\delta = 1/n$

@SureshVenkat Musisz użyć twierdzenia PCP, które mówi, że lepsze niż 7/8 przybliżenie do 3SAT to NPHard. Dlatego chcę ref;).

— Sariel Har-Peled

δ

$\delta$

δ

$\delta$

P

$P$

(1 + δ)

$(1+\delta)$

P

$P$

ϵ

$\epsilon$

ϵ = δ

$\epsilon = \delta$