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.

1
Czy prawdziwą losowość (możliwe do udowodnienia) można zastąpić losowością Kołmogorowa dla RP?
Czy były jakieś próby wykazania, że losowość Kołmogorowa byłaby wystarczająca dla RP ? Czy prawdopodobieństwo użyte w stwierdzeniu „Jeśli prawidłowa odpowiedź brzmi TAK, to wówczas (probabilistyczna maszyna Turinga) zwraca TAK z prawdopodobieństwem ...” zawsze byłoby dobrze zdefiniowane w takim przypadku? Czy byłyby tylko górne i dolne granice tego prawdopodobieństwa? Czy …
1
Czy pseudolosowość deterministyczna jest prawdopodobnie silniejsza niż przypadkowość równolegle?
Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do losowego strumienia bitów ustalonego przy uruchomieniu algorytmu.N CBPPBPP\mathsf{BPP}NCNC\mathsf{NC} …
3
Jaka jest najszybciej znana symulacja BPP z wykorzystaniem algorytmów Las Vegas?
BPPBPP\mathsf{BPP} iZ P PZPP\mathsf{ZPP} to dwie podstawowe probabilistyczne klasy złożoności. B P PBPP\mathsf{BPP} jest klasą języków ustaloną przez probabilistyczne algorytmy Turinga w czasie wielomianowym, w których prawdopodobieństwo zwrotu nieprawidłowej odpowiedzi przez algorytm jest ograniczone, tzn. Prawdopodobieństwo błędu wynosi maksymalnie13)13\frac{1}{3} (zarówno dla wystąpień TAK, jak i NIE). Z drugiej strony, algorytmy …
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 …
1
Jakie jest prawdopodobieństwo, że losowa funkcja boolowska ma trywialną grupę automorfizmów?
Biorąc pod uwagę funkcję boolowską , mamy grupę automorfizmów .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Czy są jakieś znane granice dla ? Czy jest coś znanego dla ilości postaci dla jakiejś grupy ?Prf(Aut(f)≠1)Prf(Aut(f)≠1)Pr_f(Aut(f) \neq 1)Prf(G≤Aut(f))Prf(G≤Aut(f))Pr_f(G \leq Aut(f))GGG
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.