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.

1
Więcej na temat PH w PP?
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym …
3
Dlaczego losowość ma większy wpływ na redukcje niż na algorytmy?
Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez losowe wielomianowe skrócenie czasu. Jest mało prawdopodobne, …
6
Wydajne i proste randomizowane algorytmy, w których determinizm jest trudny
Często słyszę, że w przypadku wielu problemów znamy bardzo eleganckie algorytmy randomizowane, ale nie ma, lub tylko bardziej skomplikowane, deterministyczne rozwiązania. Znam jednak tylko kilka przykładów. Najbardziej widoczne Randomized Quicksort (i powiązane algorytmy geometryczne, np. Dla wypukłych kadłubów) Randomized Mincut Testowanie tożsamości wielomianowej Problem Klee'a Spośród nich jedynie testowanie tożsamości …
2
Derandomizacja Valiant-Vazirani?
Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie, że UNIQUE-SAT jest NP- twardy przy randomizowanych redukcjach. Z zastrzeżeniem prawdopodobnych przypuszczeń …
2
Hierarchia dla BPP a derandomizacja
W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii złożoności?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Moim motywem do tego pytania jest zrozumienie względnej trudności (w odniesieniu do innych głównych …
3
Problemy z nie są znane z ?
Jakie problemy należą do ale nie są znane z ?BPPBPP\mathsf{BPP}PP\mathsf P Mówiąc dokładniej, interesują mnie niezależne problemy, czyli takie, których derandomizacje nie są znane jako równoważne. Na przykład wiadomo, że derandomizacja PIT i wieloczynnikowe wielomianowe rozkładanie na czynniki są równoważne i uważałbym je za jeden problem. Motywacją mojego pytania jest …
4
Jakie konkretne dowody istnieją dla P = RP?
RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym. P = RP wynika z zależności w złożoności obwodu. Impagliazzo i Wigderson wykazali, …
1
Konsekwencje ?
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq \mathsf{P}/\text{poly} Twierdzenie Adlemana jest czasem nazywane „protoplastą argumentów derandomizacji”. Uważa się, że podlega derandomizacji, podczas gdy nie ma dowodów na to, że „kwantowość” mogłaby …
4
Czy istnieje odpowiednik derandomizacji dla algorytmów kwantowych?
W przypadku niektórych algorytmów randomizowanych można go zdemandomizować, usuwając (przy możliwym koszcie w czasie wykonywania) użycie bitów losowych i maksymalizując pewną dolną granicę celu (zwykle obliczaną na podstawie faktu, że twierdzenia dotyczą oczekiwanej wydajności losowej algorytm). Czy istnieje odpowiednik algorytmów kwantowych? Czy są jakieś dobrze znane wyniki „dekwantyzacji”? A może …
2
Funkcja boolowska, która nie jest stała w podprzestrzeniach afinicznych o wystarczająco dużym wymiarze
Interesuje mnie wyraźna funkcja boolowska fa:0 , 1n→0 , 1fa:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznejfafaf , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .0 , 1n0,1n\\{0,1\\}^no ( n )o(n)o(n) Nie jest trudno wykazać, że funkcja symetryczna nie spełnia tej właściwości, …
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.