Pytania otagowane jako query-complexity

1
Naturalne, niestabilne właściwości wykresu
Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.) Wykres ma -far od posiadania właściwości, jeśli nie …
3
Wymień czas i złożoność zapytań
Praca bezpośrednio ze złożonością czasu lub dolnymi granicami obwodu jest przerażająca. Dlatego opracowujemy narzędzia takie jak złożoność zapytań (lub złożoność drzewa decyzyjnego), aby uzyskać kontrolę nad dolnymi granicami. Ponieważ każde zapytanie zajmuje co najmniej jeden krok jednostkowy, a obliczenia między zapytaniami są liczone jako wolne, złożoność czasu jest co najmniej …
3
Modele obliczeń ściśle między klasycznym a kwantowym pod względem złożoności zapytań
Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań . Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań? Separacja może być włączona specyficzne problemy: model X oblicza funkcję ze znacznie większą liczbą zapytań niż kwantowe, …
1
Wykorzystanie dodatkowej mocy metody negatywnego przeciwnika
Negatywna metoda przeciwnika ( A D V±ZAreV.±ADV^\pm ) to SDP, który charakteryzuje złożoność kwantowych zapytań. Jest to uogólnienie powszechnie stosowanej metody przeciwnika ( ) i pokonuje dwie bariery, które utrudniały metodę przeciwnika:A D VZAreV.ADV Bariera testowania właściwości: jeśli wszystkie wystąpienia 0 są daleko od wszystkich 1 wystąpień, wówczas metoda przeciwnika …
1
Algorytm optymalizacji drzew decyzyjnych
tło Binarne drzewo decyzja TTT jest zakorzenione drzewo gdzie każdy węzeł wewnętrzny (i korzeń) jest oznaczony przez indeks w j∈{1,...,n}j∈{1,...,n}j \in \{1,..., n\} taki sposób, że żadna ścieżka od korzenia do liścia nie powtarza indeksu, liście są oznaczone wyjściami w {A,B}{A,B}\{A,B\} , a każda krawędź jest oznaczona przez 000 dla …
1
Złożoność informacji algorytmów zapytań?
Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów. Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w …
1
Czy algorytmy kwantowe z przyspieszeniem wykładniczym można ponownie odczytać za pomocą programów zakresu?
Wiadomo, że dolna granica ogólnego przeciwnika charakteryzuje złożoność kwantowych zapytań z powodu przełomowej pracy Reichardta i in. Ta sama linia pracy ustanawia również połączenia ze strukturą programu zakresu do projektowania algorytmów kwantowych. Wiele interesujących algorytmów kwantowych, w tym z przyspieszeniem wykładniczym, takich jak algorytm Simona i algorytm Shora do wyszukiwania …
1
Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym
Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z zapytaniami o członkostwo i co …
4
Ograniczanie luki między kwantową a deterministyczną złożonością zapytań
Chociaż znane są wykładnicze separacje między złożonością kwantowych zapytań o ograniczonym ograniczeniu ( Q ( f)Q(f)Q(f) ) a złożonością deterministycznych zapytań ( D ( f)D(f)D(f) ) lub złożonością losowych zapytań o ograniczonym ograniczeniu ( R ( f)R(f)R(f) ), dotyczą one tylko niektórych funkcji częściowych. Jeśli funkcje cząstkowe mają jakieś specjalne …
1
Programy rozpiętości, rozmiar świadka i złożoność certyfikatu
Program zakresu to liniowo-algebraiczny sposób określania wprowadzonej tutaj funkcji boolowskiej . Ostatnio model ten został użyty do wykazania, że ​​metoda negatywnego przeciwnika zapewnia ścisłą charakterystykę (przynajmniej do ) złożoności kwantowych zapytań.logn/loglognlog⁡n/log⁡log⁡n\log n/ \log \log n Miarą złożoności łączącą programy zakresu z kwantową złożonością zapytań jest wielkość świadka. Ta miara wydaje …
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.