Najbardziej znane asymptotyczne rozmiary PCP / 3-SAT

9

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ź.nO(nlogn)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.

Dmytro Taranovsky
źródło

Odpowiedzi:

7

Najnowocześniejsze w przypadku PCP, które dają redukcję do (78+ε) 3-SAT (nawet dla podstałych ε) to Dana Moshkovitz i Ran Raz , które mają długośćn1+o(1). Nie wiem jednak, czy ktoś próbował obliczyć dokładną zależność długościε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 npolylogndzię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.

Lub Meir
źródło
Dziękuję Ci; obie części były pomocne. Zbieram ten quasilinearny rozmiar PCP z zapytaniami O (1) i stały błąd pozostaje otwartym problemem.
Dmytro Taranovsky
Nie, tak naprawdę wynika to z prac Ben-Sassona i Sudanu. Problemem otwartym jest uzyskanie takich PCP z nieregularnym błędem.
Lub Meir
1
Szukałem trochę więcej, a Dinur 2007 rozszerza artykuł, który zacytowałeś w drugim akapicie, aby go pokazaćSATPCP12,1[log2n+O(loglogn),O(1)]. Jeśli dobrze rozumiem, oznacza to zmniejszenie 3-SAT do jakiegoś quasilinearnego rozmiaru1ε 3-SAT, ale wynik cytowany w pierwszym akapicie jest nieistotny, ponieważ daje nam 7/8+εi więcej.
Dmytro Taranovsky
Tak, to jest poprawne. Zapomniałem wspomnieć o wyniku Dinura, dodam go do odpowiedzi.
Lub Meir