Zufälligkeit ist unter anderem eine Schlüsselkomponente probabilistischer Algorithmen, vieler kombinatorischer Argumente, der Analyse von Hashing-Funktionen und der Kryptographie.
Die Frage, die mich interessiert, bezieht sich auf die Erzeugung zufälliger Permutationen. Was ist der effizienteste Weg, um eine gleichmäßig zufällige Permutation von nnn Elementen zu erzeugen, wenn ein probabilistisches paarweises Swap-Gate als Grundbaustein gegeben ist ? Hier nehme ich...
Ich suche eine endgültige Antwort darauf, ob die Erzeugung von "wirklich zufälligen" Zahlen für Turing berechenbar ist oder nicht. Ich weiß nicht, wie ich das genau ausdrücken soll. Diese StackExchange-Frage zum Thema "Effiziente Algorithmen für die Zufallsgenerierung" kommt der Beantwortung meiner...
Ich habe kürzlich folgendes gehört: "Eine nicht deterministische Maschine ist nicht dasselbe wie eine probabilistische Maschine. In groben Zügen ist eine nicht deterministische Maschine eine probabilistische Maschine, in der Wahrscheinlichkeiten für Übergänge nicht bekannt sind." Ich habe das...
Kürzlich haben Gil Kalai und Dick Lipton einen schönen Artikel über eine interessante Vermutung geschrieben, die von Peter Sarnak, einem Experten für Zahlentheorie und Riemannsche Hypothese, vorgeschlagen wurde. Vermutung. Sei die Möbius-Funktion . Angenommen, ist eine Funktion mit Eingabe in Form...
Viele glauben, dass . Wir wissen jedoch nur, dass in der zweiten Ebene der Polynom-Hierarchie liegt, dh . Ein Schritt zum besteht darin, es zuerst auf die erste Ebene der zu bringen, dh .B P P B P P ⊆ & Sigma; P 2 ∩ & Pgr; P 2 B P P = P B P P ⊆ N PB P P = P ≤ N PBPP=P⊆NP\mathsf{BPP} =...
In einem Satz: Würde die Existenz einer Hierarchie für irgendwelche implizieren?B P T I M EBPTichME\mathsf{BPTIME} Eine verwandte, aber vage Frage lautet: Bedeutet die Existenz einer Hierarchie für irgendwelche schwierigen Untergrenzen? Trifft die Lösung dieses Problems auf eine bekannte Barriere...
Ein Computer mit einem unendlichen Strom von wirklich zufälligen Bits ist leistungsfähiger als ein Computer ohne. Die Frage ist: Ist es mächtig genug, um das Halteproblem zu lösen? Kann ein probabilistischer Computer feststellen, ob ein deterministisches Programm anhält oder nicht ? Beispiel für...
Im Zusammenhang mit dem Slither-Link- Puzzle habe ich mich gefragt: Angenommen, ich habe ein Gitter aus quadratischen Zellen, und ich möchte einen einfachen Zyklus von Gitterkanten finden, der unter allen möglichen einfachen Zyklen gleichmäßig zufällig ist.n×nn×nn\times n Ein Weg, dies zu tun,...
In einer wissenschaftlichen Arbeit aus dem Jahr 2002 haben Mezard, Parisi und Zecchina die Heuristik der Glaubensausbreitung für zufällige 3SAT vorgestellt. Experimente zeigen, dass die Heuristik gut für Verhältnisse von Bedingungen pro Variable funktioniert, für die wahrscheinlich eine...
Gibt es eine (sinnvolle) Möglichkeit, eine gleichmäßig zufällige boolesche Funktion deren Grad als reales Polynom höchstens beträgt ?df:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd EDIT: Nisan und Szegedy haben gezeigt, dass eine Funktion des Grades von höchstens Koordinaten abhängt , daher...
Gibt es ein Beispiel für ein natürliches Problem, das in BPP vorkommt, bei RP oder Co-RP jedoch nicht bekannt
Luca Trevisan hat gezeigt, wie viele Konstruktionen von Pseudozufallsgeneratoren tatsächlich als Extraktorkonstruktionen betrachtet werden können: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Gibt es eine sinnvolle Unterhaltung? Kann man sich "natürliche" Konstruktionen von Extraktoren...
Wenn fff eine konvexe Funktion ist, dann besagt Jensens Ungleichung, dass f(E[x])≤E[f(x)]f(E[x])≤E[f(x)]f(\textbf{E}[x]) \le \textbf{E}[f(x)] ist und mutatis mutandis, wenn fff konkav ist. Natürlich kann man im schlimmsten Fall E[f(x)]E[f(x)]\textbf{E}[f(x)] in Bezug auf
Gibt es eine gute Umfrage, die verschiedene Extraktoren, Konzentratoren und Superkonzentratoren vergleicht und die besten Methoden in Bezug auf den Kompromiss zwischen Zufälligkeit, Zeit und Raum aufzeigt?
Zwei verwandte Fragen zum Bounded-Depth-Computing: 1) Angenommen, Sie beginnen mit n Bits, und um mit Bit i zu beginnen, können Sie mit einer gewissen Wahrscheinlichkeit p (i) unabhängig 0 oder 1 sein. (Wenn es das Problem einfacher macht, können wir annehmen, dass alle p (i) s 0,1 oder 1/2...
Wurden Untersuchungen zur Implementierung von Zufallsextraktorkonstruktionen durchgeführt? Es scheint, dass Extractor-Proofs Big-Oh verwenden, was die Möglichkeit für große versteckte Konstanten lässt und programmatische Implementierungen möglicherweise unrealistisch macht. Kontext: Ich bin daran...
Ist es möglich, eine explizite -Matrix mit zu erstellen , sodass jede -Matrix weniger als ?0 / 1 N 1,5 N 0,499 × N 0,499 N 0,501N× NN×NN \times N 0 / 10/10/1N1.5N1.5N^{1.5}N0,499× N0,499N0.499×N0.499N^{0.499} \times N^{0.499}N0,501N0.501N^{0.501} Oder es ist wahrscheinlich möglich, eine explizite...
In dieser Frage scheinen wir ein natürliches Problem identifiziert zu haben, das unter randomisierten Reduktionen NP-vollständig ist, möglicherweise jedoch nicht unter deterministischen Reduktionen (obwohl dies davon abhängt, welche unbewiesenen Annahmen in der Zahlentheorie zutreffen). Sind noch...
Eine Distribution soll -fool eine Funktion wenn . Und es wird gesagt, dass es eine Klasse von Funktionen täuscht, wenn es jede Funktion in dieser Klasse täuscht. Es ist bekannt, dass durch voreingenommene Räume die Klasse der Paritäten über Teilmengen täuschen. (siehe Alon-Goldreich-Hastad-Peralta...
Soweit mir bekannt ist, verwenden die meisten Implementierungen der Erzeugung von Pseudozufallszahlen in der Praxis Methoden wie Linear Shift Feedback Register (LSFRs) oder diese "Mersenne Twister" -Algorithmen. Obwohl sie viele (heuristische) statistische Tests bestehen, gibt es keine...