Pytania otagowane jako circuit-complexity

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

5
Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona
Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ = 0(max(n,m))1+ϵ(max(n,m))1+ϵ(\max(n,m))^{1+\epsilon}ϵ=0ϵ=0\epsilon=0
3
Czy
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta …
1
Współczynniki Fouriera Funkcje boolowskie opisane przez obwody o ograniczonej głębokości z bramkami AND OR i XOR
Niech faff będzie funkcją boolowską i pomyślmy o f jako funkcji od {−1,1}n{−1,1}n\{-1,1\}^n do {−1,1}{−1,1}\{ -1,1 \} . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te 2n2n2^n monomialów stanowią podstawę dla przestrzeni funkcji rzeczywistych na {−1,1}n{−1,1}n\{-1,1\}^n . Suma kwadratów współczynników wynosi …
3
Pojęcie monotonicznych obwodów kwantowych
W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że ​​3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy dla obwodów monotonicznych (lub więcej niż jednego)? Czy istnieje kwantowe twierdzenie Razborowa?
3
Konstruktywność w dowodzie naturalnym i złożoność geometryczna
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są spełnione i że możemy zdecydować, czy funkcja docelowa w (lub innej „twardej” klasie złożoności) ma …
2
Dolne granice wielkości formuły dla funkcji AC0
Pytanie: Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)Ω(n2)\Omega(n^2) Tło: Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły powyżej standardowego uniwersalnego zestawu bram {AND, OR, NOT}. …
4
Jaka jest „najmniejsza” klasa złożoności, dla której znane jest obwody superliniowe?
Przepraszamy za zadawanie pytań, które z pewnością muszą znaleźć się w wielu standardowych źródłach. Ciekawi mnie dokładnie pytanie zawarte w tytule, w szczególności myślę o obwodach boolowskich, bez ograniczeń głębokości. W cudzysłowie wstawiam „najmniejszy”, aby umożliwić istnienie wielu różnych klas, o których nie wiadomo, że zawierają się w sobie, dla …
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.