Twardość hałaśliwych funkcji boolowskich

Niech będzie funkcją boolowską zmiennych boolowskich. Niech będzie oczekiwaną wartością gdy jest uzyskane z poprzez odwrócenie każdej współrzędnej z prawdopodobieństwem .n g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ /$f$$n$$g(x)=T_\epsilon (f) (x)$$f(y)$$y$$x$$\epsilon/2$

Interesują mnie przypadki, w których przybliżenie jest trudne obliczeniowo . Pozwól, że ustalę pojęcie „przybliżenia” (ale mogą istnieć inne): Funkcja boolowska przybliża jeśli gdy i gdy . Argument liczenia (oparty na istnieniu kodów korygujących błąd dodatniej stopy) wydaje się wskazywać, że istnieją funkcje boolowskie, dla których takie przybliżenie wymaga obwodu wielkości wykładniczej. Ale pytanie brzmi, co się stanie, gdy na początek będzie w NP lub w jego sąsiedztwie.h g h ( x ) = 1 g ( x ) ≥ 0,9 h ( x ) = 0 g ( x ) ≤ 0,1 $g$$h$$g$$h(x)=1$$g(x)\ge 0.9$$h(x)=0$$g(x)\le 0.1$$f$

P1: Czy istnieje przykład opisany przez obwód NP (lub przestrzeń P), tak że każda jest NP trudna lub trudna w nieco słabszym sensie?$f$$h$

Aby zobaczyć, że może nie zawsze być łatwe (dziękuję Johanowi Hastadowi za przydatną dyskusję na ten temat), możemy rozważyć właściwość grafów posiadania kliki o rozmiarze , dla losowego wprowadzania można sobie wyobrazić, że trudno jest wykryć, czy istnieje duża klika, ale objawia się to tym, że na hałaśliwym wykresie ma więcej niż oczekiwano klików o rozmiarze log n. W takim przypadku każda będzie prawdopodobnie trudna (ale nie do udowodnienia i nie strasznie trudna, jak mówią obwody quasi-wielomianowe).n 1 / 4$h$$n^{1/4}$$h$

Q2: Jaka jest sytuacja, jeśli na początek ma niską złożoność. ( , monotoniczny , itp.)A C 0 T C 0 A C $f$$AC^0$$TC^0$$ACC$

P3: Jaka jest sytuacja niektórych podstawowych przykładów funkcji boolowskich. (Pytanie można rozszerzyć również na funkcję o wartości rzeczywistej.)

P4: Czy powyższe pytanie można formalnie zadać dla jednolitego modelu obliczeniowego (maszyny Turinga)?

Aktualizacja: W świetle odpowiedzi Andy'ego (Cześć, Andy) Myślę, że najciekawszym pytaniem jest zrozumienie sytuacji dla różnych określonych funkcji.

Zaktualizuj Kolejne pytanie Q5 [Q1 dla funkcji monotonicznych] (również w świetle odpowiedzi Andy'ego). Jaka jest sytuacja, gdy jest monotoniczny? Czy nadal możemy solidnie zakodować NP pełne pytania>$f$

w przypadku pytania 1 odpowiedź brzmi „tak” i można ją przedstawić w następujący sposób. (Będę również domyślnie naszkicować twierdzącą odpowiedź na pytanie 4, ponieważ argument jest jednolity i potraktuje wszystkie długości wejściowe naraz).

Napraw dowolny język kompletny dla NP i rodzinę dobrych binarnych kodów korygujących błędy (powiedzmy ze współczynnikiem 1/4 i poprawianiem z części .1 błędów, powiedzmy). Niech będzie funkcją kodowania dla długości ; używamy takiego kodu, w którym jest obliczalny przez jednolity algorytm czasu wielomianowego.E n c n : { 0 , 1 } n → { 0 , 1 } 4 n n E n c = { E n c n$L$$Enc_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$$n$$Enc = \{Enc_n\}$

Zdefiniuj jako zbiór ciągów które są w odległości co najwyżejod słowa kodu kodujący jakiś element . Należy pamiętać, że jest w NP, jak można się domyślać i sprawdzić pobliski słowa kodowego, zdekodowany słowo, a certyfikat NP do członkostwa dekodowany wyrazu w . z .05 | z | y ∈ E n c ( L ) L L ′$L'$$z$$.05 |z|$$y \in Enc(L)$$L$$L'$$L$

Zatem twierdzenie jest takie, że jakiekolwiek „przybliżenie” w twoim znaczeniu jest NP-trudne dla . Bo jeśli weźmiemy pod uwagę ważnego słowa kodowego pewnej długości , to z prawdopodobieństwem nad losowe wersji -perturbed z , to zgadzam się z w co najwyżej. 05 ułamka współrzędnych, a zatem nie zgadza się z żadnym innym słowem kodowym w więcej niż ułamku współrzędnych. Dla takiego mamy IFF . Więc jeśli ε = .01 y = E n c ( x ) 4 n 1 - o ( 1 ) ε y ′ y y E n c n .05 y ′ y ′ ∈ L ′ x ∈ L h ε L ′ h ( y ) = L ( x ) E n c L h $L'$$\varepsilon = .01$$y = Enc(x)$$4n$$1 - o(1)$$\varepsilon$$y'$$y$$y$$Enc_n$$.05$$y'$$y' \in L'$$x \in L$$h$jest jakimkolwiek przybliżeniem do wygładzonej wersji w twoim znaczeniu, wtedy musimy mieć . Ponieważ jest wydajnie obliczalny, daje nam to sposób na efektywne zredukowanie pytań członkowskich dla do pytań na . Więc jest trudne NP.$\varepsilon$$L'$$h(y) = L(x)$$Enc$$L$$h$$h$

Dwie notatki:

(1) kodowania korygujące błędy instancji NP były wcześniej używane w kilku artykułach, w szczególności
D. Sivakumar: On Membership Comparable Sets. J. Comput. Syst. Sci. 59 (2): 270–280 (1999).

(2) powyższy argument oczywiście nie mówi nic o średniej złożoności każdego problemu NP, ponieważ korekcja błędów jest stosowana dla poszczególnych instancji.