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)$ $\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ż , 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ę , zapisujemy odpowiedzi na wszystkich dane wejściowe (czas potrzebny ); następnie zliczamy wszystkie obwody na wejściach w rosnącym rozmiarze, aż zostanie znaleziony jeden, który da wszystkie poprawne odpowiedzi. Wyszukiwanie kończy się albo wielkością trywialnej konwersji, $\mathsf{DTIME(t(n))}$ $n$ $2^n$ $(2^n)t(n)$ $n$ lub tablica prawdy funkcji, jeśli wyjściami są . (Edycja: Thomas wskazuje, że granica to 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$

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ą!

cc.complexity-theory circuit-complexity uniformity

— usul
źródło

1,2,3,4: Funkcja tożsamości. 5. nie jest dla mnie jasne, co rozumiesz przez „konwersję algorytmów w obwody”, zawsze możemy przekształcić jednolity obwód w maszynę Turinga (z niewielkim narzutem).

— Kaveh

n

$n$

n^{3}

$n^3$

n^{3}

$n^3$

n^{3}

$n^3$

@Kaveh: Jak funkcja tożsamości odpowiada na 1-4?

— Joshua Grochow

@Joshua, możemy bezpośrednio opisać jednolity obwód o rozmiarze (drutu) O (n), który jest lepszy niż konwersja maszyny Turinga do identyfikacji na obwód.

— Kaveh

Chodzi mi o to, że są ważne drobne szczegóły, o które musimy dbać, aby na pytanie można było odpowiedzieć. Kolejny przykład: BPP jest w P / poli, a konwersja jest obliczalna. Jeśli generowanie obwodu odbywa się za pomocą wydajnego algorytmu, połączenie go z wartością obwodu da wydajną TM. Koncepcyjnie obwód i TM obliczają ten sam algorytm. Fakt, że rozmiar i czas mogą nie odpowiadać dokładnie, jest normalny, są one zdefiniowane dla różnych modeli obliczeniowych i wiemy, że nie odpowiadają. Prawdopodobnie czas bardziej odpowiada głębokości niż wielkości.

— Kaveh

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).

— Thomas wspiera Monikę
źródło

Dzięki, masz rację, intuicyjnie chciałem wykluczyć ten przypadek „górnej granicy”, ale nie znałem właściwej asymptozy. Zredagowałem pytanie, aby uwzględnić tę sprawę.

— usul