Czy istnieją znane funkcje z następującą właściwością sumy bezpośredniej?

To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek (choć oczywiście nie mamy żadnych wyraźnych przykładów). Załóżmy, że chciałbym oszacować tę samą funkcję M razy, dla jakiejś liczby całkowitej M, na M różnych zestawach danych wejściowych, tak aby całkowita liczba danych wejściowych wynosiła MN. Oznacza to, że po prostu chcesz ocenić dla tej samej funkcjiF,w każdym momencie.$f(x_{1,1},...,x_{1,N}), f(x_{2,1},...,x_{2,N}),...,f(x_{M,1},...,x_{M,N})$$f$

Pytanie brzmi: czy wiadomo, że istnieje ciąg funkcji (jedna funkcja dla każdego N), tak że dla dowolnego N, dla dowolnego M, całkowita wymagana liczba bramek jest co najmniej równa M razy funkcja wykładnicza N? Prosty argument liczenia nie wydaje się działać, ponieważ chcemy, aby ten wynik był ważny dla wszystkich M. Można wymyślić proste analogi tego pytania w teorii złożoności algebraicznej i innych obszarach.$f$

Cóż, to nieprawda: możliwe jest oszacowanie M kopii KAŻDEGO f przy użyciu tylko bramek O (N (M + 2 ^ N)), które mogą być znacznie mniejsze niż M * exp (N) (w rzeczywistości amortyzacja liniowa jest amortyzowana złożoność wykładniczego M). Nie pamiętam referencji, ale myślę, że może ona wyglądać następująco:

Najpierw dodaj 2 ^ N fikcyjnych danych wejściowych, które są tylko stałymi 0 ... 2 ^ N-1, a teraz oznaczają i-te N-bitowe wejście xi (więc dla i <= 2 ^ N mamy xi = i, a dla 2 ^ N <i <= 2 ^ N + M mamy oryginalne dane wejściowe). Teraz tworzymy tryplet dla każdego z wejść M + 2 ^ N: (i, xi, fi), gdzie fi to f (i) dla pierwszych wejść 2 ^ N (stała, która jest wbudowana w obwód), a fi = "*" Inaczej. Teraz sortujemy trojaczki (i, xi, fi) zgodnie z kluczem xi i pozwólmy, aby j-ta trójka była (i_j, x_j, f_j) z tego obliczamy trójkę (i_j, x_j, g_j), pozwalając g_j być f_j jeśli f_j nie jest „*” i niech g_j będzie g_ (j-1) w przeciwnym razie. Teraz posortuj nowe trojaczki z powrotem według klucza i_j, a otrzymasz poprawne odpowiedzi w odpowiednich miejscach.

Jest jeszcze jeden wynik, który dodatkowo ogranicza możliwości tego rodzaju zjawiska sumy bezpośredniej, którego szukasz. Dobrze znany wczesny wynik Shannona (zaostrzony przez Lupanova) wykazał, że wszystkie funkcje boolowskie są obliczalne na podstawie obwodów o wielkości , a argumentacja Shannona, że ​​jest to funkcja losowa, jest ścisła. Można by pomyśleć, że przynajmniej dla umiarkowanych wartości m złożoność obwodu obliczeń m wystąpień losowego f skalowałaby się jako m 2 n / n . Jednak Dietmar Uhlig pokazał się w$O(2^n/n)$$m$$m$$f$$m 2^n/n$

„Sieci obliczające funkcje boolowskie dla wielu wartości wejściowych”

$m = 2^{o(n/\log n)}$$m$$f$$O(2^n/n)$$m = 1$

Nie mogę znaleźć niechronionej kopii online ani strony głównej dla autora, ale natknąłem się na artykuł w tym postępowaniu:

Boolean Function Complexity (London Mathematical Society Lecture Note Series)

Jeśli chodzi o złożoność algebraiczną, nie znam przykładu, w którym złożoność wykładnicza sprowadza się do sub-wykładniczej zamortyzowanej złożoności, ale przynajmniej istnieje prosty przykład, że złożoność M rozłącznych kopii może być znacznie mniejsza niż M razy złożoność pojedynczej kopii :

Dla „losowej” n * n macierzy A złożoność postaci dwuliniowej zdefiniowanej przez A (funkcja f_A (x, y) = xAy, gdzie x i y są 2 wektorami o długości n) wynosi Omega (n ^ 2 ) - może to być pokazane przez argument wymiaru „zliczający”, ponieważ potrzebujesz n ^ 2 „miejsc” w obwodzie, aby wstawić stałe. Jednak biorąc pod uwagę n różnych par wektorów (x ^ 1, y ^ 1) ... (x ^ n, y ^ n), możesz umieścić x w rzędach macierzy X * n macierzy, i podobnie y do kolumn macierzy Y, a następnie przeczytaj wszystkie odpowiedzi x ^ iAy ^ i z przekątnej XAY, gdzie jest to obliczane w operacjach n ^ 2.3 (lub tak) przy użyciu szybkiego mnożenia macierzy, znacznie mniej niż n * n ^ 2.

Zostało to zbadane i rozwiązane przez Wolfganga Paula, który pokazał zasadniczo, co jest omawiane.