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ź.
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.
źródło