Praktyczne konsekwencje

10

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

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

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

[FSS81], [Ajt83]: .ZAdo0


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

  1. Czy możemy obliczyć w praktyce za pomocą obwodów E C 0 ?EC0

  2. Co z nieograniczonym wachlarzem AND / OR? Czy możemy je obliczyć w ?EC0

  3. Czy ma jakieś praktyczne konsekwencje? Czy A C 0 jest ważne w praktyce?AC0AC0

  4. Dlaczego ważne dla (teoretycznych) informatyków?AC0


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:

Kaveh
źródło
to rodzina obwodów BOOLEAN, takich jak A C 0, ale z ograniczonym wachlarzem. Nie wiem dużo o złożoności obwodów, więc nie mogę powiedzieć, czy elektronika równa się wartości logicznej. Wiem jednak z architektury komputerowej, że wszystkie bramki można zrealizować za pomocą tranzystorów. Ponieważ masz ograniczony fanin, myślę, że masz również ograniczoną liczbę tranzystorów, więc nie naruszasz ograniczonej głębokości i wielomianu. NC0Ado0
chazisop
@chazisop: Wszystkie funkcje logiczne można zaimplementować za pomocą AND / OR / NOT, chodzi o to, czy implementacja ma wymaganą formę, tj. wielomianowo wiele części i ograniczona głębokość. Należy zauważyć, że C 0 można alternatywnie zdefiniować za pomocą łopatki wentylatora w punkcie 2 i / lub bramy, ale liczba naprzemiennych bramek w układzie powinna być ograniczona. (Być może będę musiał dokładniej zdefiniować, co rozumiemy przez głębokość dla obwodu elektronicznego, jeśli nie jest to jeszcze zdefiniowane w literaturze).ZAC0
Kaveh
Z tego, co pamiętam z moich studiów licencjackich (czytaj: niewiele), rzeczywiste obwody w twoim komputerze nie są acykliczne - mają pętle sprzężenia zwrotnego i stan, i być może lepiej są modelowane jako skończone automaty. Wydaje mi się, że jeśli istnieje rozdźwięk między wynikami na temat a wynikami, które można zastosować do laptopa, jest to kluczowe rozróżnienie, zamiast używania tranzystorów do implementacji bramek AND. ZAdo0
Aaron Roth,
@Aaron: Ja też niewiele pamiętam, ale myślę, że pętle dotyczyły głównie elementów pamięci, takich jak flipflops i systemy sekwencyjne. Nie sądzę, że trudno jest powiązać złożoność obwodów z obwodami logicznymi / cyfrowymi, zwłaszcza z układami kombinatorycznymi, chodzi o to, jak powiązać pojęcia takie jak głębokość i wtyk z obwodami elektronicznymi wykonanymi z tranzystorów. Może powinienem o to zapytać na stronie Physics.SE.
Kaveh
3
@Tsuyoshi Ito: Dzięki. Właśnie sprawdzałem to na Wikipedii, wydaje się, że można łatwo zaimplementować nieograniczone bramki AND i OR za pomocą liniowej liczby NMOS . Struktura obwodów jest prosta i nie zmienia się wraz z liczbą wejść do bramki. Z drugiej strony obwód XOR wykonany z tranzystorów NMOS wydaje się bardziej skomplikowany, nie wiem, czy dobrze skaluje się ze wzrostem wachlarza.
Kaveh

Odpowiedzi:

10

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

Hermann Gruber
źródło
Rzeczywiście bardzo interesujące.
Antonio E. Porreca,
6

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.

David
źródło
2
dziękuję za odpowiedź, ale duża część twojej odpowiedzi to komentarze skierowane do Johna, a nie do moich pytań. Rozumiem, że prawdopodobnie umieściłeś to jako odpowiedź, ponieważ nie możesz komentować, ale nie chcę, aby to pytanie przerodziło się w dyskusję między wami dwoma, więc czy mógłbyś przenieść część swojej odpowiedzi, która jest skierowana do niego na powiązane pytanie wysłany przez niego? (lub do meta dyskusji ) Z góry dziękuję.
Kaveh
1

1.622)3,822)

s=zabdojan

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.

nO(1)

ZAT.2)=Ω(n2))

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

λ(3))=8

XYZ=X(YZ+YZ)+X(YZ+YZ)

μ(3))

X1X2)Xn

4(n-1)

johne
źródło
Tahnks johne za odpowiedź, ale w tej chwili brakuje mi trochę czasu, ale przeczytam twoją odpowiedź uważniej i przejrzę artykuły, do których linkujesz, kiedy znajdę trochę wolnego czasu. Rozmawiałem również z przyjaciółmi z działu EE i nauczyłem się kilku interesujących rzeczy, które opublikuję.
Kaveh