Kekerasan APX tidak menyiratkan QPTAS?

Jadi, pencarian cepat di web membuat saya percaya bahwa "APXHardness menyiratkan bahwa tidak ada QPTAS untuk suatu masalah kecuali [beberapa kelas kompleksitas] termasuk dalam beberapa [kelas kompleksitas lain]" dan ini juga dikenal! Sepertinya semua orang tahu ini kecuali aku. Sayangnya, tidak ada referensi untuk mendukung pernyataan ini. Saya punya dua pertanyaan:

Apa versi terkuat dari pernyataan ini yang saat ini dikenal?
Referensi? Silahkan?

Terima kasih sebelumnya.

Jawaban Chandra Chekuri ini menunjukkan bahwa untuk masalah -Hard menyiratkan . Adakah yang bisa menjelaskan mengapa itu benar, atau lebih baik memberikan referensi untuk itu? Dengan kata lain, mengapa kuasi perkiraan waktu polinomial menyiratkan solvabilitas waktu QP? $QPTAS$ $APX$ $NP\subseteq QP$

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

Jawaban untuk pertanyaan ini: cstheory.stackexchange.com/questions/9350/… menunjukkan bahwa sangat tidak mungkin bahwa MAX 3SAT menerima sesuatu yang lebih baik daripada 7/8 dalam waktu subeksponensial (tidak mungkin dikondisikan pada ETH).

Suresh Venkat

Jawaban:

$\delta > 0$ $(1+\delta)$ $P=NP$ $P \neq NP$

$\delta > 0$ $(1+\delta)$ $\delta > 0$ $(1+\delta)$ $n^{O(\log n)}$ $n^{O(\log n)}$

Chandra Chekuri
sumber

Kenapa (PTAS

⟹

$\implies$ Berarti P = NP) (QPTAS

⟹ N P \subseteq Q P

$\implies NP\subseteq QP$

N P \subseteq Q P

$NP\subseteq QP$

@chandra Yeh. Itu bisa dipercaya, ref? (Kecuali untuk secara eksplisit melalui rincian kekerasan perkiraan untuk 3SAT dan seterusnya, yang tidak sulit, tetapi seorang ref akan lebih baik ...)

Sariel Har-Peled

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

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

δ = 1 / n

$\delta = 1/n$

@ SureshVenkat Anda perlu menggunakan teorema PCP yang mengatakan bahwa melakukan lebih baik dari 7/8 pendekatan ke 3SAT adalah NPHard. Itu sebabnya saya ingin referensi;).

Sariel Har-Peled

δ

$\delta$

δ

$\delta$

P

$P$

(1 + δ)

$(1+\delta)$

P

$P$

ϵ

$\epsilon$

ϵ = δ

$\epsilon = \delta$