Pytania otagowane jako circuit-complexity

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

4
Czy istnieją znane funkcje z następującą właściwością sumy bezpośredniej?
To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek (choć oczywiście nie mamy żadnych wyraźnych przykładów). Załóżmy, że chciałbym …
1
Wymiar VC wielomianów nad tropikalnymi półksiężycami?
BPP\mathbf{BPP}P\mathbf{P}poly\mathrm{poly} (max,+)(max,+)(\max,+)(min,+)(min,+)(\min,+) Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , f i ( x ) = Y IFF ı ∈ S . Oznacza to, że wykresy dokładnie tych wielomianów f i z i ∈ …
1
Monotoniczna złożoność obwodu arytmetycznego elementarnych wielomianów symetrycznych?
W kkk -tej elementarne wielomian symetryczny Snk(x1,…,xn)Skn(x1,…,xn)S_k^n(x_1,\ldots,x_n) jest sumą wszystkich produktów różnych zmiennych. Interesuje mnie złożoność obwodu arytmetycznego monotonicznego tego wielomianu. Prosty algorytm programowania dynamicznego (jak również ryc. 1 poniżej) daje obwód z bramkami .(nk)(nk)\binom{n}{k}kkk(+,×)(+,×)(+,\times)(+,×)(+,×)(+,\times)O(kn)O(kn)O(kn) Pytanie: Czy znana jest dolna granica ? Ω(kn)Ω(kn)\Omega(kn) obwód jest skośna , jeżeli co najmniej …
2
Zwykły kontra TC0
Według Zoo Złożoności , Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1} i wiemy, że RegReg\mathsf{Reg} nie może się liczyć, więc TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg} . Jednakże nie mówi, czy Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0} czy nie. Ponieważ nie znamy NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0} , nie znamy również Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} . Czy jest kandydatem do problemu w , który nie …
1
Jak drogie może być zniszczenie wszystkich długich ścieżek w DAG?
Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone „wewnętrzny” (te, które nie ścieżki pomiędzy i ), …
1
Beigel-Tarui transformacja układów ACC
Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która jest …
1
Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?
Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie, Co najmniej takie, że SAT jest redukcją N P- twardą wr A C 0 d wielokrotności jeden?reddN …
1
Czy można udowodnić za pomocą twierdzenia Linial-Mansour-Nisan i znajomości czteroczęściowego spektrum ?
Wynik 1: Twierdzenie Linial-Mansour-Nisan mówi, że czteroliniowa waga funkcji obliczonych przez obwody jest skoncentrowana na podzbiorach małych rozmiarów z dużym prawdopodobieństwem.AC0AC0\mathsf{AC}^0 Wynik 2: ma czterokierunkową wagę skoncentrowaną na współczynniku stopnia .PARITYPARITY\mathsf{PARITY}nnn Pytanie: Czy istnieje sposób, aby udowodnić (jeśli można udowodnić), że nie jest obliczalny przez obwody przez / przy użyciu …
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.