Pytania otagowane jako circuit-complexity

Złożoność obwodu to badanie obwodów ograniczonych przez zasoby i funkcji obliczanych przez takie obwody.

2
Zakres barier naturalnych dowodów
Naturalna bariera dowodowa Razborova i Rudicha mówi, że przy wiarygodnych założeniach kryptograficznych nie można mieć nadziei na oddzielenie NP od P / poli poprzez znalezienie kombinatorycznych właściwości funkcji, które są konstruktywne, duże i użyteczne. Istnieje kilka dobrze znanych wyników, które potrafią ominąć barierę. Istnieje również kilka artykułów omawiających możliwe luki …
1
Złożoność obwodu monotonicznego funkcji obliczeniowych na rzadkich wejściach
Wagaciągu binarnego to liczba jedynek w ciągu. Co się stanie, jeśli będziemy zainteresowani obliczeniem funkcji monotonicznej na wejściach z kilkoma?x ∈ { 0 , 1 } n| x ||x||x|x ∈ { 0 , 1 }nx∈{0,1}nx\in\{0,1\}^n Wiemy, że podjęcie decyzji, czy wykres ma klasę jest trudne dla obwodów monotonicznych (patrz między …
2
PARITY
jest klasa układów wielomian wielkości stałej głębokości z nie bram i bezgranicznej fan-in i i lub bram, gdzie wejścia i bramy mają również nieograniczony Fanout.AC0AC0AC^0 Rozważmy teraz nową klasę, nazwijmy ją która jest jak A C 0, ale dla której wejścia i bramki mają co najwyżej O ( 1 ) …
1
Jawne wielomiany w 1 zmiennej o dolnych granicach złożoności obwodu superlogarytmicznego?
Zliczając argumenty, można pokazać, że istnieją wielomiany stopnia n w 1 zmiennej (tj. Coś w postaci które mają złożoność obwodu n. Można również pokazać, że wielomian taki jak wymaga co najmniej mnożenia (potrzebujesz tego tylko, aby uzyskać wystarczająco wysoki stopień). Czy są jakieś wyraźne przykłady wielomianów w 1 zmiennej o …
2
Minimalna szerokość drzewa obwodu dla WIĘKSZOŚCI
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być wielomianowy) i że dane wejściowe powinny być odczytywane tylko raz, chociaż rozwarcie bramki wejściowej może …
1
Słynny papier P = BPP Impagliazzo i Wigdersona
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P = B P PP.=bP.P.\mathsf P=\mathsf{BPP} Szukam …
2
Oszukiwanie
Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?logO ( d)( n )logO(d)⁡(n)\log^{O(d)}(n)A C.0AC0AC^0reddnnn Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy C 0 obwody głębokości D …
1
Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, …
2
Warianty bezpośrednich twierdzeń o produktach
Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kkkfafffaff Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może być obliczone przez obwody o wielkości s z prawdopodobieństwem większym …
1
Czy ludzie patrzą na zagęszczenie pętli w obwodach boolowskich?
Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz, modulo kilka szczegółów technicznych dotyczących tego, czym jest pętla i co stanowi zagnieżdżoną pętlę, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.