Twierdzenie o hierarchii wielkości obwodu

Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie.

Czy to ciekawe podejście do separacji klasowej?

Motywem tego pytania jest to, że musimy powiedzieć

istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości $f(n)$ i można ją obliczyć na podstawie obwodu wielkości , gdzie . (i być może coś odnośnie głębokości)f ( n ) < o ( g ( n ) $g(n)$$f(n)<o(g(n))$

więc jeśli , właściwość wydaje się nienaturalna (narusza warunek wielkości). Oczywiście nie możemy użyć diagonalizacji, ponieważ nie jesteśmy w jednolitym otoczeniu.$f(m)g(n) \leq n^{O(1)}$

Czy w tym kierunku jest wynik?

W rzeczywistości można wykazać, że dla każdego wystarczająco małego (mniej niż 2 n / n ) istnieją funkcje obliczalne dla obwodów o wielkości f ( n ), ale nie przez obwody o wielkości f ( n ) - O ( 1 ) lub nawet f ( n ) - 1 , w zależności od typu dozwolonych bramek.$f$$2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Oto prosty argument, który pokazuje, że istnieją funkcje obliczalne w rozmiarze ale nie w rozmiarze f ( n ) - O ( n ) .$f(n)$$f(n)-O(n)$

Wiemy to:

1. istnieje funkcja która wymaga złożoności obwodu co najmniej 2 n / O ( n ) , aw szczególności złożoności obwodu większej niż f ( n ) .$g$$2^n/O(n)$$f(n)$
2. funkcja taka, że z ( x ) = 0 dla każdego wejścia x jest obliczalne przez obwód o stałej wielkości.$z$$z(x)=0$$x$
3. Jeśli dwie funkcje i g 2 różnią się tylko jedno wejście, a ich złożoność obwodu różni się co najwyżej o O ( n $g_1$$g_2$$O(n)$

Załóżmy, że jest niezerowe na wejściach N. Zaproszenie takie wejścia x 1 , ... , x N . Możemy rozważyć dla każdego i funkcję g i ( x ), która jest funkcją wskaźnika zestawu { x 1 , … , x i } ; zatem g 0 = 0 a g N = g .$g$$N$$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Oczywiście istnieją pewne takie, że g i + 1 ma złożoność obwodu większą niż f ( n ), a g i ma złożoność obwodu mniejszą niż f ( n ) . Ale wtedy g i ma złożoność obwodu mniejszą niż f ( n ), ale większą niż f ( n ) - O ( n ) .$i$$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Ten wynik można udowodnić za pomocą prostego argumentu liczenia. Rozważ losową funkcję zastosowaną do pierwszych bitów wejścia. Ta funkcja prawie na pewno ma złożoność obwodu ( 1 + o ( 1 ) ) ( 2 k / k ) według argumentu liczącego Riordana i Shannona i dopasowuje górne granice. Zatem wybierając k tak, aby 2 g ( n ) < 2 k / k < f ( n ) / 2 , można było rozróżnić rozmiar $k$$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ od rozmiaru f ( n ) . Zauważ, że funkcje, o których mowa, niekoniecznie będą obliczalne, ale możemy umieścić je w wykładniczej hierarchii czasu za pomocą standardowych technik (o ile możemy obliczyć odpowiednią wartość k ). Oczywiście nie możemy udowodnić żadnego wiązania większego niż 2 n / n , ponieważ jest to najgorszy przypadek złożoności obwodu dowolnej funkcji. $g(n)$$f(n)$$k$$2^n/n$

Naturalne dowody nie mają zastosowania do tego rodzaju argumentów, ponieważ przedmiotowa właściwość `` nie ma małego obwodu '', co nie jest łatwe do obliczenia z tabeli prawdy funkcji (przypuszczalnie). Nie jest jasne, jak niski w klasach złożoności może być ten rodzaj liczenia. Czy jest jakiś powód, dla którego nie można użyć argumentu liczenia udowodnić dolne granice dla ? Nie żebym o tym wiedział. $NE$