Praktyczne konsekwencje

tło

Obwód złożoność C 0 jest zdefiniowany jako zbiór rodzin obwodu (tj sekwencje obwodów, po jednym dla każdej wielkości wejściowej) o ograniczonej głębokości i wielomianu wielkości zbudowany przy użyciu nieograniczona fan-in AND, OR i NOT.$AC^0$

Funkcja parzystości z wejściem n- bitowym jest równa XOR bitów na wejściu.$\oplus$$n$

Jednym z pierwszych obwodów o niższej granicy, sprawdzonym pod względem złożoności obwodu, jest:

[FSS81], [Ajt83]: .$\oplus \notin AC^0$

Pytania:

Niech będzie klasą funkcji, które można obliczyć za pomocą obwodów elektronicznych o ograniczonej głębokości i wielomianu przy użyciu części elektronicznych, takich jak tranzystory. (Wymyśliłem nazwę E C 0 , daj mi znać, jeśli znasz na to lepszą nazwę).$EC^0$$EC^0$

1. Czy możemy obliczyć w praktyce za pomocą obwodów E C 0 ?$\oplus$$EC^0$

2. Co z nieograniczonym wachlarzem AND / OR? Czy możemy je obliczyć w ?$EC^0$

3. Czy ma jakieś praktyczne konsekwencje? Czy A C 0 jest ważne w praktyce?$\oplus \notin AC^0$$AC^0$

4. Dlaczego ważne dla (teoretycznych) informatyków?$\oplus \notin AC^0$

Uwaga:

Ten post zawiera interesujące pytania, ale OP wydaje się odmawiać uczynienia tego postu bardziej czytelnym i z jakiegoś powodu naprawiam w nim nieporozumienie, więc odpowiadam na nie. (Łatwiej byłoby edytować oryginalny post, ale obecnie nie ma umowy, jeśli można znacznie edytować post innego użytkownika).

Związane z:

• Parzystość i $AC^0$

• Dlaczego parzystość nie ważna w A C 0 ? $AC^0$(Blog o złożoności obliczeniowej)

Nie jestem inżynierem elektrykiem, ale szukam patentów online dotyczących obwodów przełączających dla bramek parzystości, a wszystkie propozycje (znalazłem patenty dopiero do końca lat siedemdziesiątych) omawiają problem wielkości z głębokością. Wszystkie trzy patenty, na które patrzyłem, proponują rozwiązania o logarytmicznej głębokości, oparte na bramkach fanin-2. Zatem odpowiedź na twoje pierwsze pytanie brzmi „nie”.

JJ Moyer: Parity Check Switching Circuit, patent Stanów Zjednoczonych US3011073, 1961

AF Bulver i in .: NAND Gate realizacja funkcji parzystości n-wejściowej, patent Stanów Zjednoczonych US3718904, 1973

PJ Baun, Jr .: Parity Circuits, patent Stanów Zjednoczonych US 4251884, 1981

Johne, jaki masz problem? Próbujesz kłócić się o rzeczy, o których nikt nigdy nie twierdził. Nikt nie powiedział, że dolna granica parzystości stanowi pewną podstawową granicę dla obliczania XOR z obwodami innymi niż te, do których stosuje się to twierdzenie (tj. Obwody AC ^ 0). Nie ma tu żadnych ukrytych założeń ani ukrytych implikacji. W szczególności wszyscy wiemy na przykład, że możliwe jest obliczenie XOR z wielomianowymi obwodami NAND o logarytmicznej głębokości, nawet przy stałym wachlowaniu.

Cytat Shannona jest również w dużej mierze nieistotny. Nic nie wskazuje na to, że podejrzewał nawet, że obwody AND-OR o stałej głębokości muszą mieć wykładniczy rozmiar, aby obliczyć parzystość. Oczywiście mógł się domyślić, ponieważ łatwo jest przypuszczać, że powinno to być prawdą po dłuższej zabawie z problemem, ale co z tego?

Brakuje Ci zupełnie sedna: udowodnienie, że dolne granice jest niezwykle trudne, i musimy gdzieś zacząć od najprostszych modeli. Był to zasadniczo pierwszy dolny obwód, techniki doprowadziły do ​​wielu interesujących pomysłów (w tym innych dziedzin, takich jak teoria uczenia się) i chociaż wynik jest wiarygodny, dowód jest wnikliwy i wcale nie trywialny.

Fakt, że wynik wydaje się intuicyjny, nie czyni tego oczywistym; jeśli tak uważasz, proszę przedstawić dowód, że parzystości nie ma w AC ^ 0. Wszyscy wiedzą, że P również nie jest równe NP, ale nikt nie jest bliski posiadania dowodu.

Twoje skargi w innych wątkach na temat bram NAND również nie mają sensu. Ta dolna granica obowiązuje równie dobrze dla obwodów o stałej głębokości zbudowanych z bramek NAND, ponieważ są one zasadniczo takie same. Wybór podania wyniku za pomocą AND, OR, NOT jest tylko kwestią wygody. Może to być więc aplikacja w świecie rzeczywistym pod względem, który lubisz: obwody o stałej głębokości obliczania parzystości bramek NAND wymagają wykładniczej wielkości. Daje to praktyczne ograniczenie, nawet jeśli nie jest to najważniejsze. Mówi, że małe obwody XOR dla dużej liczby n wejść muszą mieć albo głębokość rosnącą z n, albo bramki inne niż NAND. Dlaczego nie jesteś z tego zadowolony?

Twierdzenie, że głębokość obwodu nie jest problemem w prawdziwym świecie, jest również bardzo mylące, ponieważ głębokość jest bezpośrednio związana z czasem i maksymalną częstotliwością, przy której zegar może działać.

Nawiasem mówiąc, społeczność CS doskonale zdawała sobie sprawę z teorii obwodów boolowskich EE i opierała się na tym, wbrew temu, co twierdzisz.

$1.62^2$$3.82^2$

• Technologia CMOS Struktury układów logicznych

$s = a \oplus b \oplus c_{in}$

• Wysoka prędkość, niska moc 8T Pełna komórka sumująca

Dobrym miejscem do znalezienia szybkich, kompaktowych bram XOR / XNOR są w pełni sumatory i obwody Hamming ECC (które zwykle znajdują się na ścieżce krytycznej).

Ponadto problem głębokości obwodu zwykle nie stanowi problemu w logice synchronicznej VLSI. Jedyną głębokością jakiejkolwiek konsekwencji jest ścieżka krytyczna, która określa maksymalny okres zegara. Zdecydowana większość logiki kombinatorycznej propaguje swoje wyniki w ułamku czasu na ścieżkę krytyczną. Ścieżki krytyczne zdarzają się z pewną kombinatoryczną logiką, która musi przejść przez kilka obszarów rozproszonych na chipie.

$n$$O(1)$

$AT^2 = \Omega(n^2)$

• O złożoności implementacji VLSI i reprezentacji graficznych funkcji boolowskich z mnożeniem aplikacji do liczb całkowitych

Pochodzi z bloga złożoności obliczeniowej:

Rodzi to pytanie: czy niektórzy ludzie w prawdziwym świecie naprawdę chcą konstruować obwody Fanin AND-OR-NOT o stałej głębokości polisize o stałej głębokości dla PARITY, a czy ten wynik mówi im, dlaczego nie mogą?

$2^n/n$

$\lambda(3) = 8$

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

$\mu(3)$

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

$4(n-1)$