Pytania otagowane jako circuit-complexity

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

1
Najmniejsza liczba bramek do mnożenia
Jaki jest najlepszy wynik dla liczby bramek w obwodzie pomnożącym dwie liczby całkowite n-bitowe? Oczywista metoda generuje bramki . Istnieją lepsze podejścia z i .θ(n2)θ(n2)\theta(n^2)θ(nlognloglogn)θ(nlog⁡nlog⁡log⁡n)\theta(n\log n \log\log n)θ(nlogn2log∗(n))θ(nlog⁡n2log∗⁡(n))\theta(n\log n2^{\log^*(n)}) Nie mogłem znaleźć żadnej rodziny obwodów boolowskich, która obsługiwałaby mnożenie za pomocą bramek . Zastanawiam się, czy istnieje taka rodzina obwodów.nlognnlog⁡nn\log …
1
Losowe ograniczenia i związek z całkowitym wpływem funkcji boolowskich
Powiedzmy, że mamy funkcję boolowską fa: { - 1 , 1}n→ { - 1 , 1 }f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} i aplikujemy δδ\delta-losowe ograniczenie na faff. Ponadto powiedz, że drzewo decyzyjneT.TT to oblicza faff zmniejsza się O ( 1 )O(1)O(1)w wyniku losowego ograniczenia. Czy to implikuje tofafaf ma bardzo niski wpływ całkowity?
2
Dokładna złożoność problemu w
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób leży problem ∩m≥2AC0[m]∩m≥2AC0[m]\cap_{m \geq 2}{\mathsf{AC}^0[m]} ponieważ x≡1modmx≡1modmx \equiv 1\bmod{m}iff . Pytanie brzmi: czy problem leży w ? …
2
Anulowanie i wyznacznik
Algorytm Berkowitza zapewnia obwód wielomianowy o głębokości logarytmicznej do wyznaczania macierzy kwadratowej z wykorzystaniem mocy macierzy. Algorytm domyślnie wykorzystuje anulowanie. Czy anulowanie jest niezbędne do uzyskania obwodu wielomianowego o głębokości logarytmicznej lub liniowej w celu obliczenia wyznacznika (i każdego możliwego najlepszego obwodu na stałe)? Czy istnieją dolne granice w pełni …
1
FO-uniform AC0 z pewnym orzeczeniem
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)FO(R) będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”. Chciałbym wiedzieć, czy jest jakakolwiek caracterization FO(&lt;,R)FO(&lt;,R)FO(<,R) z R dowolnym orzeczeniem NrNr\mathbb N^rdla jakiegoś r? Na przykład …
1
„Właściwy” warunek jednolitości dla klasy Nicka
DLOGTIME jest zdefiniowany na stronie http://en.wikipedia.org/wiki/DLOGTIME nazwa jest zdefiniowany na stronie http://en.wikipedia.org/wiki/L_%28complexity%29 nazwa i nazwa są zdefiniowane na stronie http://en.wikipedia.org/wiki/NC_%28complexity%29 LL\operatorname{L} NCNC\operatorname{NC}NCnNCn\operatorname{NC}^n DLOGTIME wydaje się być najmniejszym, który może działać. Czytałem w różnych miejscach, , chociaż każde miejsce, w jakim okazało się, że wyniki, które stwierdza warunek jednorodności używa - …
2
Próg w pełni homomorficzne kryptosystemy
ostatnio Craig Gentry opublikował pierwszy schemat szyfrowania klucza publicznego (na przestrzeni tekstu jawnego {0,1}), który jest w pełni homomorficzny, co oznacza, że ​​można skutecznie i kompaktowo oceniać AND i XOR na zaszyfrowanych tekstach jawnych bez znajomości tajnego klucza odszyfrowywania. Zastanawiam się, czy istnieje jakiś oczywisty sposób na przekształcenie tego kryptosystemu …
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.