Pytania otagowane jako sample-complexity

1
Pobieranie próbek zadowalających wzorów 3-SAT
Rozważ następujące zadanie obliczeniowe: Chcemy pobrać próbkę 3-SAT formuły zmiennych (wariant: zmiennych klauzule m ) w odniesieniu do równomiernego rozkładu prawdopodobieństwa, pod warunkiem spełnienia wzoru:nnnnnnmmm P1: Czy można to skutecznie osiągnąć za pomocą klasycznego komputera (z losowymi bitami)? P2: Czy można to skutecznie osiągnąć za pomocą komputera kwantowego? Interesują mnie …
1
Złożoność próbkowania (w przybliżeniu) transformaty Fouriera funkcji boolowskiej
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli wybranie x zgodnie z . (Znormalizowane w razie potrzeby …
2
Złożoność obliczeniowych zapytań w uczeniu się SQ
Wiadomo, że do uczenia się PAC istnieją naturalne klasy pojęć (np. Podzbiory list decyzji), w których występują wielomianowe luki między złożonością próby potrzebną do teoretycznego uczenia się informacji przez uczonego bez ograniczeń obliczeniowych a złożonością próby potrzebną przez wielomian uczący się czasu. (patrz np. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE lub http://portal.acm.org/citation.cfm?id=301437 ) Wyniki te …
1
Biorąc pod uwagę
Oto problem o smaku podobnym do nauki junt: Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca .x f ( x )fa: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\}xxxfa( x )f(x)f(x) Cel: Znajdź podmoduł S.SS o wartości { …
1
Jaka jest właściwa rola weryfikacji w próbkowaniu kwantowym, symulacji i testowaniu metodą rozszerzonego kościoła-Turinga (ECT)?
Ponieważ nie udzielono odpowiedzi, ustawiono flagę z prośbą o przekształcenie tego pytania w wiki społeczności. Komentarze Aarona Sterlinga, Sasho Nikolova i Vora zostały zsyntetyzowane do następującej rozdzielczości, która jest otwarta na dyskusję wiki społeczności: Rozwiązane: W odniesieniu do klasycznych algorytmów, które generują liczby, próbki lub trajektorie symulacji, ścisła logika matematyczna …
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.