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 P X -hard problemu oznacza N P ⊆ Q P . 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$

APX twardości oznacza, że istnieje , tak że problem ten nie dopuścić do ( 1 + δ ) -approximation chyba że P = N P . Wyraźnie wyklucza to PTAS (przy założeniu P ≠ N P ). 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 ( 1 + δ ) 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 δ > 0 a ( 1 + δ ) w czasie, powiedzmy n O ( log n ) . 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)}$