Kann ein zufälliges Orakel ändern, welche TFNP-Probleme im Durchschnitt stark sind?

Ich habe zu
verschiedenen Zeiten über die folgende Frage nachgedacht, seit ich diese Frage zur Kryptographie gesehen habe .

Frage

Sei eine TFNP- Beziehung. Kann ein zufälliges Orakel P / Poly helfen , mit nicht zu vernachlässigender Wahrscheinlichkeit zu brechen ? Formaler, $R$
$R$ $\newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}}$

Tut

für alle P / poly Algorithmen , ist vernachlässigbar $A$ $\Pr_x [R(x, A(x))]$

implizieren das unbedingt

für fast alle o racles , für alle P / poly Oracle-Algorithmen , ist vernachlässigbar $\O$ $A$ $\Pr_x [R(x, A^\O(x))]$

Alternative Formulierung

Die relevante Menge von Orakeln ist $G_{\delta\sigma}$ (also messbar). Wenn Sie also kontrapositiv sind und Kolmogorovs Null-Eins-Gesetz anwenden , entspricht die folgende Formulierung der ursprünglichen.

Tut

für fast alle o racles , es existiert ein P / poly Oracle-Algorithmus , so daß ist nicht vernachlässigbar $\O$
$A$ $\Pr_x [R(x,A^\O(x))]$

implizieren das unbedingt

Es gibt einen P / Poly-Algorithmus so dass nicht vernachlässigbar ist $A$ $\Pr_x [R(x,A(x))]$

Der einheitliche Fall

Hier ist ein Beweis für die einheitliche Version :

Es gibt nur countably-many PPT Oracle-Algorithmen, so durch zählbare Additivität der null [ideal] [8], ein PPT - Algorithmus ist , so dass für einen nicht - Null - Satz von Orakeln , ist nicht zu vernachlässigen. Sei ein solcher Orakel-Algorithmus. $A$ $\O$
$\Pr_x [R(x,A^\O(x))]$ $B$

In ähnlicher Weise lassen eine positive ganze Zahl sein , so dass für einen nicht-Null - Satz von Orakeln , ist unendlich oft mindestens , wobei die Länge die Eingabe. Durch die contra von Borel-Cantelli , $c$ $\O$
$\Pr_x[R(x,B^\O(x))]$ $n^{-c}$ $n$
ist unendlich. $\sum_{n=0}^{\infty} \Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))] \right]$

Durch den Vergleichstest ist unendlich oft . $\Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x)) \right] \geq n^{-2}$

Sei der PPT-Algorithmus, der [das Orakel simuliert] [12] und mit diesem simulierten Orakel ausführt. $S$ $B$

Fixiere und sei die Menge der Orakel so dass . $n$ $\Good$ $\O$ $n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$

Wenn nicht null ist, dann ist $\Good$ .

\begin{matrix} \Pr_{O} [O \in G o o d] \cdot n^{- c} \\ = \\ \Pr_{O} [O \in G o o d] \cdot E_{O} [n^{- c}] \\ \leq \\ \Pr_{O} [O \in G o o d] \cdot E_{O} [\Pr_{x \in {0, 1}^{n}} [R (x, B^{O} (x))] ∣ O \in G o o d] \\ = \\ E_{O} [\Pr_{x \in {0, 1}^{n}} [O \in G o o d and R (x, B^{O} (x))]] \\ \leq \\ E_{O} [\Pr_{x \in {0, 1}^{n}} [R (x, B^{O} (x))]] \\ = \\ \Pr_{O, x \in {0, 1}^{n}} [R (x, B^{O} (x))] \\ = \\ \Pr_{x \in {0, 1}^{n}, O} [R (x, B^{O} (x))] \\ = \\ E_{x \in {0, 1}^{n}} [\Pr_{O} [R (x, B^{O} (x))]] \\ = \\ E_{x \in {0, 1}^{n}} [\Pr [R (x, S (x))]] \\ = \\ \Pr_{x \in {0, 1}^{n}} [R (x, S (x))] \end{matrix}

$\begin{matrix} \Pr_{\O} [\O\in \Good] \cdot n^{-c} \\ = \\ \Pr_{\O} [\O\in \Good] \cdot \E_{\O}[n^{-c}] \\ \leq \\ \Pr_{\O} [\O\in \Good] \cdot \E_{\O} \left[ \Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))] \mid \O \in \Good \right] \\ = \\ \E_{\O}\left[ \Pr_{x\in \{0,1\}^n} [\O \in \Good \text{ and } R(x,B^\O(x))] \right] \\ \leq \\ \E_{\O}\left[ \Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))] \right] \\ = \\ \Pr_{\O, x\in\{0,1\}^n} [R(x,B^\O(x))] \\ = \\ \Pr_{x\in \{0,1\}^n, \O} [R(x,B^\O(x))] \\ = \\ \E_{x\in \{0,1\}^n} \left[ \Pr_{\O}[R(x,B^\O(x))] \right] \\ = \\ \E_{x\in \{0,1\}^n} \left[ \Pr[R(x,S(x))] \right] \\ = \\ \Pr_{x\in \{0,1\}^n} [R(x,S(x))] \end{matrix}$

Da unendlich oft ist, ist nicht vernachlässigbar. $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ $\Pr_x[R(x,S(x))]$

Daher gilt die einheitliche Version . Der Beweis nutzt kritisch die Tatsache, dass es
nur zählbar viele PPT- Orakel-Algorithmen gibt. Diese Idee funktioniert im
ungleichmäßigen Fall nicht, da es kontinuierlich viele P / Poly-Orakel-Algorithmen gibt.

cr.crypto-security relativization advice-and-nonuniformity search-problem random-oracles Gemeinschaft
quelle

O

$\mathcal{O}$

R

$R$

A

$A$

A

$A$

A

$A$

A

$A$

O

$\mathcal{O}$

R

$R$

A

$A$

@Adam, es gibt einen anderen Quantifizierer, der wichtig ist. Ich denke, es ist einfacher, die Negation zu betrachten: Ist es möglich, dass es für fast jedes Orakel einen ungleichmäßigen Gegner gibt, der das Orakel verwenden kann, um das Suchproblem zu lösen?

Kaveh

Aha. Ich beantwortete eine andere Frage. Entschuldigung für die Verwirrung.

Adam Smith

@domotorp: Sie sollten jetzt behoben werden. (Meine beste Vermutung, warum das passiert ist, ist die

$\hspace{1.05 in}$ Verwendung von nummerierten Links , anstatt in-line Links).

Nein zu meinem Titel und Ja zum Text meiner Frage. Dies verallgemeinert sich in der Tat sofort
auf jedes Spiel mit Polynomlänge, bei dem der Code der Gegner nicht verwendet wird.

$C$ $A$

$\mathcal{O}$
$C$ $\operatorname{Pr}_x\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$

$\mathcal{O}$

$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$

$\mathcal{O}$
$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$

Sei j eine solche Anzeige und sei z der (nicht unbedingt effiziente) Orakelalgorithmus, der
n als Eingabe verwendet und die lexikographisch kleinste Orakelschaltung mit einer Größe von höchstens j + n ausgibt $^{\hspace{.03 in}j}$
$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right) \: < \: \operatorname{Prob}_{\mathcal{O}}\hspace{-0.05 in}\bigg[\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.03 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right) < \operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]\hspace{-0.06 in}\bigg] \;\;\;$ für unendlich viele n.

Für solche n,

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; = \; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \cdot \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}\hspace{.02 in},\hspace{.04 in}x\in \{0,1\}^n}\hspace{-0.06 in}\left[R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]$

$A$ $n$

$x$

$y$

$A$
$\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \:\:\:\:$ .
Sei p wie in Satz 2 und setze $\;\;\; f \: = \: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.04 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\cdot \hspace{-0.04 in}n^{(2+j)\cdot 2} \:\:\:\:$

$\mathcal{S}$ $\mathcal{P}$
$\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ dann

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)-\left(\hspace{-0.04 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)}$
$= \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.06 in} \cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)} \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)}$
$< \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right]-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)} \; \leq \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{P}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ .

Für n so dass $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ ::

$\big[$ $C$ $^{\hspace{.03 in}j}\big]$
$\big[$ $\big]$
$A$ $1$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$
$^{\hspace{.03 in}j}$

$A$ $^{\hspace{.03 in}j}$
$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$ $^{\hspace{.03 in}j}$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$ $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ , $\;\;\;$ es gibt also ein Polynom, so dass

die Sequenz, deren n-ter Eintrag die lexikographisch kleinste
[Schaltung C der Größe, die oben durch dieses Polynom begrenzt ist] ist, die maximiert $\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.04 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$

ist ein P / Poly-Algorithmus, dessen Wahrscheinlichkeit (über die Wahl von x), eine Lösung zu finden, nicht vernachlässigbar ist.

Daher gilt die Implikation im Körper meiner Frage immer.

$A$

quelle

Kann ein zufälliges Orakel ändern, welche TFNP-Probleme im Durchschnitt stark sind?

Frage

Alternative Formulierung

Der einheitliche Fall

Antworten: