Pytania otagowane jako circuit-complexity

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

1
Klasy złożoności obwodów liniowych
Klasa to funkcje klasy obliczalne przez rodziny obwodów ograniczonego wielkości i głębokości . -hierarchy jest sumą tych klas.NCjaNCi\textrm{NC}^inO ( 1 )nO(1)n^{O(1)}O ( logja( n ) )O(logi⁡(n))O(\log^i(n))NCNC\textrm{NC} Czy jest jakieś badanie wariantu wielkości hierarchicznej tej hierarchii? Czy to rodziny obwodów ograniczonego wachlarza, głębokości polilogu i rozmiaru liniowego? Wiem, że istnieje trochę …
1
Decydowanie o najbardziej znaczącym mnożeniu binarnym
Interesuje mnie określenie złożoności następującego problemu decyzyjnego: Biorąc pod uwagę dwie liczby całkowite i l 2 (każda z co najwyżej m bitami), zdecyduj, czy najbardziej znaczącym bitem z mnożenia l 1 ⋅ l 2 jest 1 (gdzie wynik jest drukowany w 2-bitowych bitach z możliwymi początkowymi zerami)?l1l1l_1l2)l2l_2l1⋅ l2)l1⋅l2l_1 \cdot l_2 …
1
Klasy złożoności losowości i małych obwodów
Niech będzie klasą złożoności, a będzie losowym odpowiednikiem zdefiniowanego jako w odniesieniu do . Bardziej formalnie podajemy wielomianowo wiele bitów losowych i akceptujemy dane wejściowe, jeśli prawdopodobieństwo akceptacji jest większe niż .Cdo\mathcal{C}BP-CBPdo\textrm{BP-}\mathcal{C}Cdo\mathcal{C}BPPBPP\textrm{BPP}PP.\textrm{P}232)3)\frac{2}{3} Wiadomo, że dla klasy obwodów nierównomiernych mamy :BPAC0= AC0BPAC0=AC0\textrm{BPAC}^0=\textrm{AC}^0 Miklós Ajtai, Michael Ben-Or: Twierdzenie o probabilistycznych obliczeniach stałej …
2
Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków
Rozważ następujący problem: Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania .MMMv↦Mvv↦Mvv \mapsto Mv Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy). Co wiadomo o tym problemie? Czy są jakieś interesujące …
1
Minimalizacja programu
Minimalizacja obwodu to problem polegający na zminimalizowaniu rozmiaru danego obwodu. Czy jest coś podobnego do programów ogólnych? W szczególności moje pytanie brzmi - Czy istnieją algorytmy minimalizujące liczbę instrukcji dla danego programu? Wiem, że to nierozstrzygalny problem, ale nie szukam rozwiązania, które zwróci coś optymalnego. Podczas gdy można zastosować wcześniej …
1
Dlaczego dolne granice dla obwodów boolowskich nie implikują niższych granic obwodów arytmetycznych
Moje pytanie brzmi: dlaczego dolne granice dla głębokości 3 Obwody logiczne z bramkami „i” i „xor” dla wyznacznika nie oznaczają takich samych dolnych granic dla obwodów arytmetycznych w ?ZZ\mathbb{Z} Co jest nie tak z następującym argumentem: Niech będzie wyznacznikiem obliczającym obwód arytmetyczny, a następnie biorąc wszystkie zmienne mod 2 otrzymamy …
1
Ile rozcięć krawędzi musi mieć DAG?
Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN to . tssstttΘ(n3)Θ(n3)\Theta(n^3) Niech być DAG (skierowane acykliczny wykres) z jednym węzłem źródłowym jeden docelowego węzła . …
3
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.AC0ZAdo0AC^0 Funkcja parzystości z wejściem n- bitowym jest równa XOR bitów na wejściu.⊕⊕\oplusnnn Jednym z pierwszych …
1
Oceń obwód logiczny na partii podobnych danych wejściowych
Załóżmy, że mam obwód boolowski CCC która oblicza jakąś funkcję f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}. Załóżmy, że obwód składa się z AND, OR i NOT bramek z wachlarzem i wachlowaniem co najwyżej 2. Pozwolić x∈{0,1}nx∈{0,1}nx \in \{0,1\}^nbyć danym wkładem. DanyCCC i xxx, Chcę ocenić CCC na nnn dane wejściowe, które różnią się …
3
Jakie są przykłady tego, jak niejednolita może być przydatna?
Ciekawi mnie, w jaki sposób niejednorodność okazała się przydatna w obliczeniach. Jednym ze sposobów jest losowość, jak wBPP⊆P/polyBPP⊆P/polyBPP \subseteq P/poly, a kolejnym są tabele przeglądowe, które służą do pokazania, że ​​wszystkie języki mają niejednolite obwody. W szczególności interesują mnie sposoby, w jakie obiekty, o których wiadomo, że istnieją za pomocą …
1
Jednolita derandomizacja klas złożoności obwodów
Pozwolić CC\mathcal{C} być klasą złożoności i BP-CBP-C\textrm{BP-}\mathcal{C} być randomizowanym odpowiednikiem CC\mathcal{C} zdefiniowane w taki sam sposób jak BPPBPP\textrm{BPP} jest zdefiniowany w odniesieniu do PP\textrm{P}. Bardziej formalnie zapewniamy wielomianowo wiele losowych bitów i akceptujemy dane wejściowe, jeśli prawdopodobieństwo, że zostanie zaakceptowane, jest zakończone2323\frac{2}{3}. W poprzednim poście zapytałem, czy wiadomo, czy równość …
2
Jaka jest „najmniejsza” klasa złożoności, dla której
Wierzę, że odpowiedzi na to pytanie dają takie klasy, że dla wszystkich wielomianówppp, w klasie występuje problem, który nie ma obwodów wielkościp ( n )p(n)p(n). Pytam jednak o rozmiar obwoduω( n )ω(n)\omega \hspace{.02 in}(n). (⟨00,11,2)2),3)1,44,51,66,71,88,91, . . .⟩(⟨00,11,22,31,44,51,66,71,88,91,...⟩\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 …
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.