Czy mamy nietrywialne jednolite obwody?

Biorąc pod uwagę algorytm działający w czasie , możemy go przekształcić w „trywialną” rodzinę obwodów jednorodnych dla tego samego problemu wielkości co najwyżej ≈ t ( n ) log t ( n ) .$t(n)$$\approx t(n)\log t(n)$

Z drugiej strony może się zdarzyć, że mamy znacznie mniejsze jednorodne obwody dla tego problemu, nawet jeśli jest optymalnym czasem działania. Obwody mogą generować dłużej niż t ( n ) , ale są małe.$t(n)$$t(n)$

Ale czy naprawdę wiemy, jak budować takie rzeczy? Myślę, że początkowe pytanie, które należy zadać, to

(1) Czy mamy jakieś konstruktywne przykłady nietrywialnych obwodów jednorodnych, tj. Obwodów jednorodnych, których rozmiar jest mniejszy niż najbardziej znany czas działania dowolnego algorytmu dla tego samego problemu?

Teraz uważam, że jeśli problem dotyczy , to mamy algorytm czasu wykładniczego, aby znaleźć optymalne obwody za pomocą wyczerpującego wyszukiwania: Biorąc pod uwagę n , zapisujemy odpowiedzi na wszystkich 2 n dane wejściowe (czas potrzebny ( 2 n ) t ( n ) ); następnie zliczamy wszystkie obwody na wejściach n w rosnącym rozmiarze, aż zostanie znaleziony jeden, który da wszystkie poprawne odpowiedzi. Wyszukiwanie kończy się albo wielkością trywialnej konwersji, t ( n ) $\mathsf{DTIME(t(n))}$$n$$2^n$$(2^n)t(n)$$n$ lub tablica prawdy funkcji, 2 n, jeśli wyjściami są { 0 , 1 } . (Edycja: Thomas wskazuje, że granica to O ( 2 n / n ) z powodu Shannona / Lupanova.)$t(n) \log t(n)$$2^n$$\{0,1\}$$O(2^n/n)$

Mamy więc niezadowalające „tak” na pytanie (1): weź język trudny przez jakikolwiek czas powyżej , ale nadal rozstrzygalny; powyższa procedura generuje tabelę prawdy o rozmiarze 2 n .$2^n$$2^n$

Powinniśmy więc sprecyzować pytanie (1). Myślę, że są dwa najbardziej interesujące przypadki

(2) Czy mamy jakieś konstruktywne przykłady nietrywialnych jednorodnych obwodów wielomianowych ? (Nawet jeśli są generowane przez bardzo wolne algorytmy.)

(3) Czy mamy jakieś konstruktywne przykłady generowanych w czasie wielomianowym nietrywialnych obwodów o wielomianowym czasie ?

To może być zbyt wiele do zadania. A może łatwiejsze pytanie: czy wiemy nawet, że coś takiego jest możliwe? Być może nie istnieją nietrywialne jednolite obwody?

$s(n) = o(2^n)$$o(2^n/n)$$L$$O(s(n))$$\tilde{O}(s(n))$

Wreszcie, jeśli powyższe pytania są zbyt trudne,

(5) Czy mamy jakieś konstrukcje jednorodnych rodzin obwodów, które nie są zwykłymi konwersjami algorytmów w obwody (lub zapisywania tabeli prawdy)?

Postscriptum. Ekspert, o którego pytanie zapytałem o wspomniane „O średniej jednorodności i obwodzie w dolnych granicach” ( pdf ), Santhanam i Williams 2013, co być może jest najbardziej zbliżoną pracą, ale dowodzi dolnej granicy (że obwody generowane w czasie nie są zbyt silny). Byłbym zainteresowany jakąkolwiek inną powiązaną pracą!

Oto odpowiedzi na dwa ostatnie pytania.

(5) Sieci sortujące to jednolite obwody, które sortują się tak szybko, jak najlepsze algorytmy RAM, ale zdecydowanie nie są to tylko konwersje algorytmów RAM (np. Quicksort). [ AKS83 , G14 ]

$s(n)=(1+\varepsilon) \cdot 2^n/n$$\varepsilon>0$$(1+o(1)) \cdot 2^n/n$$f$$\Omega(3^n)$$O(n \cdot 3^n)$$f$$O(2^n/n)$$2^{\mathrm{poly}(n)}$$\tilde{O}(2^n/n)$$s(n) = o(2^n/n)$

To interesujące pytanie; Mam nadzieję, że ktoś może odpowiedzieć (1) - (3).