APX-Härte impliziert kein QPTAS?

Eine schnelle Suche im Internet hat mich zu der Annahme geführt, dass "APXHardness impliziert, dass für ein Problem kein QPTAS vorhanden ist, es sei denn, [eine Komplexitätsklasse] ist in einer [anderen Komplexitätsklasse] enthalten", und das ist auch bekannt! Es scheint, dass jeder außer mir das weiß. Leider wird kein Hinweis zur Untermauerung dieser Aussage gegeben. Ich habe zwei Fragen:

Was ist die stärkste Version dieser Aussage, die derzeit bekannt ist?
Eine Referenz? Bitte?

Danke im Voraus.

Chandra Chekuris Antwort legt nahe, dass ein für ein -Hart-Problem impliziert . Kann jemand erklären, warum es wahr ist, oder vorzugsweise einen Hinweis darauf geben? Mit anderen Worten, warum impliziert die Quasi-Polynom-Zeit-Approximierbarkeit die QP-Zeit-Lösbarkeit? $QPTAS$ $APX$ $NP\subseteq QP$

cc.complexity-theory reference-request Sariel Har-Peled
quelle

Die Antworten auf diese Frage: cstheory.stackexchange.com/questions/9350/… zeigen, dass es höchst unwahrscheinlich ist, dass MAX 3SAT in subexponentieller Zeit etwas Besseres als 7/8 zulässt (unwahrscheinlich abhängig von der ETH).

Suresh Venkat

APX-Härte bedeutet , dass es eine , so dass das Problem nicht nicht zugeben -Anpassung , es sei denn . Dies schließt ein PTAS eindeutig aus (unter der Annahme von ). QPTAS schließt dies aus, es sei denn, Sie glauben, dass NP in quasi-polynomialer Zeit enthalten ist. Soweit ich weiß, ist dies der einzige Grund, warum APX-Härte ein QPTAS ausschließt. $\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

Da ein paar Leute mehr Details gefragt haben, hier noch ein paar mehr. Die APX-Härte für ein Minimierungsproblem P impliziert, dass es ein festes und eine Polynomzeitreduktion von 3-SAT auf P gibt, so dass eine -Näherung für P die Entscheidung zulässt, ob das 3-SAT vorliegt Formel ist erfüllbar oder nicht. Wenn es ein QPTAS für P gibt, können wir für jedes feste eine -Näherung in der Zeit erhalten, sagen wir . Dies impliziert jedoch, dass wir entscheiden können, ob eine 3-SAT-Formel in erfüllt werden kann $\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ Zeit, die wiederum impliziert, dass NP in QP ist. $n^{O(\log n)}$

Chandra Chekuri
quelle

Warum macht (PTAS

⟹

$\implies$ P = NP) Mittelwert (QPTAS

)? Bedeutet QPTAS nicht eine Approximation in quasi-polynomialer Zeit, während

eine exakte Lösung erfordert?

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

@chandra Yeh. Das ist glaubwürdig, ref? (Mit Ausnahme der expliziten Details der Näherungshärte für 3SAT und so weiter, die nicht schwer ist, aber ein Ref wäre besser ...)

Sariel Har-Peled

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

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

δ = 1 / n

$\delta = 1/n$

@SureshVenkat Sie müssen das PCP-Theorem verwenden, das besagt, dass eine bessere 7/8-Annäherung an 3SAT NPHard ist. Deshalb möchte ich einen Schiedsrichter;).

Sariel Har-Peled

@SureshVenkat das QPTAS ist nicht für 3-SAT. Es ist für das Problem P und

δ

$\delta$ ist eine feste Konstante. APX-Härte für P impliziert, dass es eine feste Konstante gibt

δ

$\delta$ so dass jeder Algorithmus, der sich löst

P

$P$ zu besser als

(1 + δ)

$(1+\delta)$ -solves 3-SAT. Die Abhängigkeit der Laufzeit des QPTAS für

P

$P$ auf

ϵ

$\epsilon$ könnte willkürlich schlecht sein, aber ich werde es nur für verwenden

ϵ = δ

$\epsilon = \delta$ das ist behoben.

Chandra Chekuri

APX-Härte impliziert kein QPTAS?

Antworten: