Pytania otagowane jako circuit-complexity

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

1
Czy
W ankiecie „Małe głębokości obwodów kwantowych” D. Bery, F. Greena i S. Homera (s. 36 z ACM SIGACT News, czerwiec 2007 t. 38, nr 2) przeczytałem następujące zdanie: Klasyczna wersja (w której bramki i mają co najwyżej stały wentylator) jest wyraźnie słabsza niż .QAC0QAC0QAC^0ANDANDANDORORORAC0AC0AC^0 Brak odniesienia do tego roszczenia. Nazwę …
2
Dolna granica wyznacznika i wartości stałej
W świetle niedawnej otchłani na głębokości 3 wynik (który między innymi daje głębokości 3 arytmetyczna obieg donxndeterminant naC) I mają następujące pytania: Grigoriev i Karpińskiokazałosię2omów(n)dolna granica dla każdego arytmetyczna obwodu głębokości-3 obliczeniowej wyznacznikanxnmacierze nad polami skończonymi (które, jak sądzę, dotyczą również Stałych). Wzór Ryserana obliczenie Stałego daje obwód arytmetyczny o …
2
Obwody dolne granice i złożoność Kołmogorowa
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że .SSSTTTxxxSSSK(x)≥TK(x)≥TK(x) \geq T Niech będzie funkcją …
1
Czy
Czy istnieje jakakolwiek prawdopodobna hipoteza złożoności / kryptografii, która wyklucza możliwość, że obwody wielomianowe mają rozmiar podwykładniczy (tj. z ) ograniczoną głębokością ( ) obwody? ϵ&lt;1d=O(1)2)O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ &lt; 1ϵ&lt;1\epsilon<1re= O ( 1 )d=O(1)d = O(1) Wiemy, że każdą funkcję obliczalną przez obwód można obliczyć na podstawie obwodu głębokości (używając …
2
Czy dodawanie można przeprowadzić na głębokości mniejszej niż 5?
Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) C 0 rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż uzyskana za pomocą algorytmu carry look forward?AC0AC0AC^0 Czy są …
2
Czy obwody AND i OR P-są kompletne?
Bramka AND &amp; OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND &amp; OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR? Moja motywacja do rozwiązania tego …
6
Referencje na temat dolnych granic obwodu
Preambuła Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do rozpoznawania języka). Dlatego w tym poście użyję tych …
2
Dolne granice dla formuł o stałej głębokości?
Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC 0, również nie są obliczalne na podstawie wzoru o stałej głębokości. Ponieważ jednak jest to łatwiejszy model, …
6
Jaki jest najlepszy sposób na uzyskanie rzutu monetą zbliżoną do uczciwej z identycznych monet tendencyjnych?
(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą jest zobowiązany.) Załóżmy, że mamy nnn identycznych monet o nastawieniu δ=P[Head]−P[Tail]δ=P[Head]−P[Tail]\delta=P[Head]-P[Tail] . …
2
Relacja między
Niech będzie klasą wszystkich zwykłych języków.REGREG\mathsf{REG} Znane jest i . Ale czy istnieje jakaś charakterystyka języków w \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}REG⊄AC0REG⊄AC0\mathsf{REG} \not\subset \mathsf{AC}^0AC0∩REGAC0∩REG\mathsf{AC}^0 \cap \mathsf{REG}
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.