Pytania otagowane jako derandomization

Każdy algorytm zrandomizowany można zasymulować za pomocą algorytmu deterministycznego, kosztem wykładniczego wzrostu czasu działania. Derandomizacja polega na przekształcaniu zrandomizowanych algorytmów w wydajne algorytmy deterministyczne.

3
Algorytmy randomizowane przy użyciu stosu
Opracowałem nową technikę derandomizacji, która ma na celu rekurencyjne algorytmy randomizowane (lub) bardziej ogólnie algorytmy randomizowane, które wykorzystują stos. Niestety nie mogłem znaleźć naturalnych, losowych algorytmów do zastosowania moich technik. Rekurencyjne łańcuchy Markowa i gramatyki stochastyczne są bardzo zbliżone do tego, czego szukam. Czy istnieją inne (bardziej naturalne) randomizowane algorytmy, …
1
O derandomizacji wielomianowych testów tożsamości
W teście tożsamości wielomianowej szukamy algorytmu deterministycznego, aby wnioskować o równości dwóch wielomianów . Ważnym otwartym problemem jest derandomizacja znanych skutecznych algorytmów randomizowanych i wytwarzanie wydajnego algorytmu deterministycznego. Czy istnieje kompletny problem dla PIT, tak że derandomizacja testów tożsamości dla tej jednej klasy wielomianów rozwiązuje ten otwarty problem? Jeśli nie, …
1
Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?
Niech k>0k>0k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą nnn , chcemy skonstruować permutację σ∈Snσ∈Sn\sigma \in S_n tak aby: Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji. Biorąc pod uwagę i∈[n]i∈[n]i\in[n] , σ(i)σ(i)\sigma(i) można obliczyć w stałym czasie i przestrzeni. …
1
Jakie są wyniki algorytmów szacujących wielomiany dla danego zestawu punktów?
Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub …
1
Jednolity sposób kwantyfikacji „rozgałęzień” w obliczeniach niedeterministycznych, probabilistycznych i kwantowych?
Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń maszyn probabilistycznych i kwantowych. (Należy zauważyć, że dla niektórych celów lepiej jest nie wyświetlać powiązanego …
4
Konstrukcje lepsze niż losowe.
Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe. Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe. Można łatwo skonstruować takie sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których …
1
Czy badano derandomizację lekko niejednorodnych klas, np. BPP / liniowy?
Przez BPP / linear mam na myśli maszyny BPP z liniową radą, która spełnia obietnicę, gdy otrzyma „prawidłową” radę, a derandomizacja powinna dać nam, powiedzmy, algorytm P / liniowy lub (SUBEXP / liniowy). Jeśli zastosujemy niejednolite założenia, uważam, że klasyczne wyniki powinny zadziałać, ponieważ możemy „oszukać” niejednolitych przeciwników. Jednak przy …
1
Jednolita derandomizacja klas złożoności obwodów
Pozwolić CC\mathcal{C} być klasą złożoności i BP-CBP-C\textrm{BP-}\mathcal{C} być randomizowanym odpowiednikiem CC\mathcal{C} zdefiniowane w taki sam sposób jak BPPBPP\textrm{BPP} jest zdefiniowany w odniesieniu do PP\textrm{P}. Bardziej formalnie zapewniamy wielomianowo wiele losowych bitów i akceptujemy dane wejściowe, jeśli prawdopodobieństwo, że zostanie zaakceptowane, jest zakończone2323\frac{2}{3}. W poprzednim poście zapytałem, czy wiadomo, czy równość …
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.