Najbardziej znane asymptotyczne rozmiary PCP / 3-SAT

Jakie są najbardziej znane asymptotyczne górne granice wielkości dowodów probabilistycznie sprawdzalnych? Idealnie szukam współczesnej ankiety dotyczącej tego szerokiego pytania, ale jeśli jej nie ma, szczególnie interesuje mnie niedopuszczalność 3-SAT.

Niech 7/8 + ε-3-SAT będzie 3-SAT z obietnicą, że jeśli 7/8 + ε część klauzul jest zadowalająca, to instancja jest zadowalająca. Jakie są najbardziej znane redukcje 3-SAT z klauzulami do 7/8 + ε-3-SAT? Na przykład, czy istnieje redukcja przy użyciu klauzul ? ( klauzule to otwarty problem). Zmniejszenie jednolitego quasilinearnego rozmiaru NC? Jaka jest zależność od ε , w tym kiedy ε → 0 ? Czy istnieje znana redukcja rozmiaru liniowego (zależna od ε ) od (1-ε) -3-SAT do 7/8 + ε-3-SAT, a jeśli nie, czy mamy lepsze granice dla (1-ε) -3 -SAT? Interesująca byłaby nawet częściowa odpowiedź.$n$$O(n \log n)$$O(n)$$ε$$ε→0$$ε$

Ponadto, chociaż może to uczyniłoby to pytanie zbyt szerokim, powinienem wspomnieć, że kolejnym ważnym problemem są stałe czynniki, które z powodu technik takich jak długi kod są zwykle niewiarygodnie duże.

Najnowocześniejsze w przypadku PCP, które dają redukcję do $(\frac{7}{8}+\varepsilon)$ 3-SAT (nawet dla podstałych $\varepsilon$) to Dana Moshkovitz i Ran Raz , które mają długość$n^{1 + o(1)}$. Nie wiem jednak, czy ktoś próbował obliczyć dokładną zależność długości$\varepsilon$lub złożoność obliczeniowa redukcji. Ich główny wynik techniczny został później uproszczony przez Irit Dinur i Prahladh Harsha .

Jeśli interesują Cię krótkie PCP ze stałą liczbą zapytań, które niekoniecznie zapewniają optymalną redukcję twardości aproksymacji (inaczej „PCP o wysokim błędzie”), to najnowocześniejszym wynikiem są PCP długości $n\cdot \mathrm{poly}\log n$dzięki Eli Ben-Sassonowi i Madhu Sudanowi i jego poprawie przez Dinura . Ponownie nie wiem, czy ktokolwiek jest dokładną złożonością obliczenia redukcji.