Pytania otagowane jako randomness

Losowość jest kluczowym składnikiem algorytmów probabilistycznych, wielu argumentów kombinatorycznych, analizy funkcji haszujących oraz w kryptografii, między innymi.

11
Jaki jest najskuteczniejszy sposób generowania losowej permutacji na podstawie probabilistycznych zamian par?
Pytanie, które mnie interesuje, dotyczy generowania przypadkowych permutacji. Biorąc pod uwagę probabilistyczną bramę wymiany par jako podstawowy element konstrukcyjny, jaki jest najbardziej skuteczny sposób na uzyskanie jednolicie losowej permutacji elementów? Tu stosować „probabilistyczny bramy parami wymiany” się operacja, która realizuje brama Przełączanie do wybranych elementów i z pewnym prawdopodobieństwem , …
7
Naprawdę generator liczb losowych: obliczanie Turinga?
Szukam ostatecznej odpowiedzi na pytanie, czy generowanie „prawdziwie losowych” liczb jest obliczalne przez Turinga. Nie wiem, jak to dokładnie sformułować. Pytanie StackExchange dotyczące „wydajnych algorytmów do generowania liczb losowych” jest bliskie odpowiedzi na moje pytanie. Charles Stewart mówi w swojej odpowiedzi: „To [losowości Martina-Löfa] nie może być wygenerowane przez maszynę”. …
9
Jaka jest różnica między niedeterminizmem a przypadkowością?
Niedawno to usłyszałem - „Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”. Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)? Edycja 1: Aby wyjaśnić, cytat …
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 …
4
Czy probabilistyczna maszyna Turinga może rozwiązać problem zatrzymania?
Komputer z nieskończonym strumieniem naprawdę losowych bitów jest potężniejszy niż komputer bez niego. Pytanie brzmi: czy jest wystarczająco silny, aby rozwiązać problem zatrzymania? Czy komputer probabilistyczny może ustalić, czy program deterministyczny przestaje działać? Przykład, w którym komputer probabilistyczny robi coś, czego deterministycznie nie można: Rozważmy mały program (o długości mniejszej …
1
Losowy sam unikający się cykl kratowy w obrębie danego obwiedni
W związku z układanką Slither Link zastanawiałem się: Załóżmy, że mam siatkę kwadratowych komórek i chcę znaleźć prosty cykl krawędzi siatki, równomiernie losowy wśród wszystkich możliwych prostych cykli.n × nn×nn\times n Jednym ze sposobów na to byłoby użycie łańcucha Markowa, którego stanami są zbiory kwadratów, których granice są prostymi cyklami …
1
Propagacja przekonań dla rzeczywistego przybliżenia 3LIN?
W artykule naukowym z 2002 r. Mezard, Parisi i Zecchina przedstawili heurystyczną propagację przekonań dla losowego 3SAT. Eksperymenty wskazują, że heurystyka działa dobrze dla współczynników ograniczeń na zmienną, dla których prawdopodobne jest istnienie zadowalającego przypisania. Moje pytania to: (1) Co się stanie, jeśli weźmiesz pod uwagę losowy 3LIN zamiast losowego …
1
Losowe funkcje niskiego stopnia jako prawdziwy wielomian
Czy istnieje (rozsądny) sposób na pobranie próbki losowo jednakowej funkcji boolowskiej której stopień rzeczywistej wielomianu wynosi co najwyżej ?df:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd EDYCJA: Nisan i Szegedy wykazali, że funkcja stopnia zależy od co najwyżej współrzędnych , więc możemy założyć, że . Problemy, które widzę, są następujące: 1) Z jednej strony, jeśli …
2
Ogranicza się do
Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy istnieje jakieś standardowe ograniczenie, które określa …
3
Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …
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.