Pytania otagowane jako boolean-functions

Pytania o funkcje boolowskie i ich analiza

2
Reprezentująca funkcję logiczną przez wielomian
Załóżmy, że mamy funkcję boolowską od . Oczywiste jest, że prawdziwy wielomianowy wielomian p ( x ) taki, że f ( x ) = p ( x ) na x ∈ { 0 , 1 } n może być wieloliniowy. Jakie są ciekawe klasy funkcji boolowskich, dla których minimalny stopień …
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ę …
1
Prawidłowa nauka PAC 2-DNF w jednolitym rozkładzie
Jaki jest najnowszy wynik w zakresie złożoności zapytań dotyczących prawidłowych formuł uczenia się PAC 2-DNF z przykładowymi zapytaniami i w jednolitym rozkładzie ? A może jakieś nietrywialne ograniczenia? Ponieważ w ogóle nie znam teorii uczenia się, a to pytanie jest motywowane inną dziedziną, odpowiedź może być oczywista. Sprawdziłem książkę Kearnsa …
1
Czy nastąpił jakiś postęp w zaostrzaniu wykładnika, w wyniku którego niezależność ?
Braverman wykazały, że rozkład które -wise niezależnie -fool głębokość obwody wielkości o "sklejanie" The Smolensky aproksymacja i aproksymacja Fouriera funkcji logicznych . Autor i ci, którzy przypuszczali, że to pierwotnie przypuszczają, że wykładnik tam można zredukować do( l o gmϵ)O (re2))(losolmϵ)O(re2))(log \frac{m}{\epsilon})^{O(d^2)}ϵϵ\epsilonrered ZAdo0ZAdo0AC^0mmmZAdo0ZAdo0AC^0O ( d)O(re)O(d)i jestem ciekawy, czy poczyniono postępy …
1
Jakie jest prawdopodobieństwo, że losowa funkcja boolowska ma trywialną grupę automorfizmów?
Biorąc pod uwagę funkcję boolowską , mamy grupę automorfizmów .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Czy są jakieś znane granice dla ? Czy jest coś znanego dla ilości postaci dla jakiejś grupy ?Prf(Aut(f)≠1)Prf(Aut(f)≠1)Pr_f(Aut(f) \neq 1)Prf(G≤Aut(f))Prf(G≤Aut(f))Pr_f(G \leq Aut(f))GGG
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?
1
Entropia głośnego rozkładu
Powiedzmy, że mamy funkcję f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R}takie, że a jest rozkładem, tzn. .∀x∈Zn2f(x)∈{12n,22n,…,2n2n},∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},fff∑x∈Zn2f(x)=1∑x∈Z2nf(x)=1\sum_{x\in \mathbb{Z}_2^n} f(x) = 1 Entropia Shannona dla jest zdefiniowana następująco: fffH(f)=−∑x∈Zn2f(x)log(f(x)).H(f)=−∑x∈Z2nf(x)log⁡(f(x)).H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) . Niech będzie niezmienny. Powiedzmy, że …
1
Dolne granice funkcji progowej
W złożoności drzewa decyzyjnego funkcji boolowskiej bardzo dobrze znaną metodą dolnej granicy jest znalezienie (przybliżonego) wielomianu reprezentującego funkcję. Paturi podał charakterystykę symetrycznych funkcji boolowskich (częściowych i całkowitych) pod względem oznaczonej ilościΓΓ\Gamma: Twierdzenie ( Paturi ): Niechfff być dowolną niestałą funkcją symetryczną i oznaczać fk=f(x)fk=f(x)f_k=f(x) kiedy |x|=k|x|=k|x|=k (tj. masa młota wynosząca …
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.