Dokładna złożoność problemu w

9

Pozwolić xi{1,0,+1} dla i{1,,n}, z obietnicą, że x=i=1nxi{0,1} (gdzie suma się skończyła Z). Jaka jest złożoność ustalenia, czyx=1?

Zauważ, że w trywialny sposób leży problem m2AC0[m] ponieważ x1modmiff . Pytanie brzmi: czy problem leży w ? Jeśli tak, to co świadczy o tym obwód? Jeśli nie, to jak to udowodnić?x=1AC0

SamiD
źródło
Ten problem może być trywialny, ale nie znam odpowiedzi i byłbym bardzo zainteresowany.
SamiD

Odpowiedzi:

7

Możesz użyć zwykłego argumentu lematu przełączającego. Nie wyjaśniłeś, w jaki sposób reprezentujesz swoje dane wejściowe w formacie binarnym, ale przy jakimkolwiek rozsądnym kodowaniu następująca funkcja jest AC równoważna twojej funkcji: (Zakładamy, że jest parzyste). Po tych notatkach z wykładów przypuśćmy, że można obliczyć z obwodu głębokości o rozmiarze . Następnie losowe ograniczenie danych wejściowych pozostawia co najwyżej funkcję złożoności drzewa decyzyjnego0

f(x1,,xn)={0if x1x2+x3x4+xn=0,1if x1x2+x3x4+xn=1,?otherwise.
nfdnbnn1/2d2d(b+1)+1 z prawdopodobieństwem co najmniej . Obliczenia prawdopodobnie pokażą, że jest to kolejna instancja (przy mniejszym rozmiarze wejściowym) z prawdopodobieństwem , a więc istnieje pewne losowe ograniczenie, które daje zarówno instancję na Wejścia i funkcja o stałej złożoności drzewa decyzyjnego, co prowadzi do sprzeczności. Ten sam argument powinien dawać wykładnicze dolne granice.11/(3n)fΘ(1/n)fn1/2d
Yuval Filmus
źródło
Myślę, że całkowita czułość tej funkcji będzie również wynosić , więc prawdopodobnie możesz użyć tego, aby uzyskać wykładniczą dolną granicę w mojej odpowiedzi. Cytowany tam wynik wykorzystuje twierdzenie Linial-Mansour-Nisan, które samo używa lematu przełączającego + proste granice spektrum funkcji o niskiej złożoności drzewa decyzyjnego. Θ(n)
Sasho Nikolov
7

Nie sądzę, że jest to w AC0 i mogę pokazać dolną granicę dla pokrewnego problemu obietnicy rozróżnienia między a , gdy . Podobne techniki Fouriera powinny mieć zastosowanie do twojego problemu, ale tego nie zweryfikowałem. A może jest prosta redukcja.xi=0xi=2x{1,1}n

Załóżmy, że jest rozmiarem głębokość obwód, który oblicza się funkcję tak, że gdy . Ponieważ dla losowego prawdopodobieństwo, że wynosi , a dla każdego takiego jest współrzędne zmieniające wartość , całkowity wpływ wynosisdf:{1,1}n{0,1}f(x)=ixiixi{0,2}xixi=02n(nn/2)n1/2xn/2ffΩ(n1/2), czyli mniej więcej tyle samo, co większość (ponieważ uwzględniono większość wrażliwych danych większości). Twierdzenie Hastada (patrz Colorraly 2.5 w notatkach Ryana O'Donnela ) oznacza, że

s2Ω(n1/(2d2)).
Sasho Nikolov
źródło