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.
Funkcja parzystości z wejściem n- bitowym jest równa XOR bitów na wejściu.
Jednym z pierwszych obwodów o niższej granicy, sprawdzonym pod względem złożoności obwodu, jest:
[FSS81], [Ajt83]: .
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ę).
Czy możemy obliczyć w praktyce za pomocą obwodów E C 0 ?
Co z nieograniczonym wachlarzem AND / OR? Czy możemy je obliczyć w ?
Czy ma jakieś praktyczne konsekwencje? Czy A C 0 jest ważne w praktyce?
Dlaczego ważne dla (teoretycznych) informatyków?
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:
Dlaczego parzystość nie ważna w A C 0 ? (Blog o złożoności obliczeniowej)
Odpowiedzi:
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
źródło
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.
źródło
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.
Pochodzi z bloga złożoności obliczeniowej:
źródło