Czy losowa wyrocznia może zmienić, które problemy TFNP są średnio trudne?

Zastanawiałem się nad następującym pytaniem w
różnych momentach, odkąd widziałem to pytanie w kryptografii .

Pytanie

Pozwolić $R$ być relacją TFNP . Czy losowa wyrocznia może pomóc P / poli
w przełamaniu z nieistotnym prawdopodobieństwem? Bardziej formalnie, $R$ $\newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}}$

Robi

dla wszystkich algorytmów P / poli , jest nieistotna $A$ $\Pr_x [R(x, A(x))]$

niekoniecznie implikuje to

w prawie wszystkich ö racles $\O$ , dla wszystkich P / poli Oracle algorytmów $A$ , $\Pr_x [R(x, A^\O(x))]$ jest nieznaczna

Alternatywne sformułowanie

Odpowiedni zestaw wyroczni to $G_{\delta\sigma}$ (w ten sposób mierzalny), więc biorąc przeciwstawne i stosując prawo Kołmogorowa równe zero , poniższe sformułowanie jest równoważne pierwotnemu.

Robi

w prawie wszystkich O racles , istnieje P / poli wyrocznia algorytm tak, że nie jest pomijalne $\O$
$A$ $\Pr_x [R(x,A^\O(x))]$

niekoniecznie implikuje to

istnieje algorytm P / poli taki, że nie jest bez znaczenia $A$ $\Pr_x [R(x,A(x))]$

Jednolity futerał

Oto dowód na jednolitą wersję :

Istnieje tylko policzalnie wiele algorytmów wyroczni PPT, więc dzięki policzalnej addytywności wartości zerowej [idealnej] [8] istnieje algorytm PPT taki, że dla zestawu wartości innych niż zerowy wyroczni , nie jest bez znaczenia. Niech będzie takim algorytmem wyroczni. $A$ $\O$
$\Pr_x [R(x,A^\O(x))]$ $B$

Podobnie, niech będzie dodatnią liczbą całkowitą taką, że dla niepustego zbioru wyroczni , jest nieskończenie często co najmniej , gdzie jest długością wejścia. Przez contrapositive z Borel-Cantelli , jest nieskończony. $c$ $\O$
$\Pr_x[R(x,B^\O(x))]$ $n^{-c}$ $n$
$\sum_{n=0}^{\infty} \Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))] \right]$

W teście porównawczym nieskończenie często . $\Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x)) \right] \geq n^{-2}$

Niech będzie algorytmem PPT, który [symuluje wyrocznię] [12] i uruchamia z tą symulowaną wyrocznią. $S$ $B$

Napraw i niech będzie zbiorem wyroczni tak, że . $n$ $\Good$ $\O$ $n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$

Jeśli nie ma wartości NULL, to . $\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 \\ {mi}_{O} [{Par}_{x \in {0, 1}^{n}} [R (x, b^{O} (x))]] \\ = \\ {Par}_{O, x \in {0, 1}^{n}} [R (x, b^{O} (x))] \\ = \\ {Par}_{x \in {0, 1}^{n}, O} [R (x, b^{O} (x))] \\ = \\ {mi}_{x \in {0, 1}^{n}} [{Par}_{O} [R (x, b^{O} (x))]] \\ = \\ {mi}_{x \in {0, 1}^{n}} [Par [R (x, S. (x))]] \\ = \\ {Par}_{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}$

Ponieważ nieskończenie często, nie jest bez znaczenia. $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ $\Pr_x[R(x,S(x))]$

Dlatego obowiązuje wersja jednolita . Dowód krytycznie wykorzystuje fakt, że istnieje
tylko niezliczona ilość algorytmów wyroczni PPT . Pomysł ten nie działa w
przypadku niejednolitego przypadku, ponieważ istnieje wiele ciągłych algorytmów P / poli oracle.

— Społeczność
źródło

Nie sądzę, żeby to było naprawdę pytanie o wyrocznie. Ponieważ jest niezależny od , możesz również dać dostęp losowemu ciągowi znaków. Pytanie brzmi zatem: czy przypadkowość zwiększa moc obwodów wielowymiarowych. Odpowiedź brzmi „nie”, ponieważ gdyby dobrze zrobił dostęp do ciągu losowego, wówczas, za pomocą argumentu uśredniającego, istniałoby określone ustawienie ciągu losowego, z którym mógłby zrobić dobrze, a my równie dobrze moglibyśmy po prostu podłącz ten ciąg do obwodu

O

$\mathcal{O}$

R

$R$

A

$A$

A

$A$

A

$A$

A

$A$

— Adam Smith

@AdamSmith: „Od jest niezależna od , może równie dobrze dać dostęp do losowy ciąg” to intuicja, ale nie widzę żadnego sposobu przekształcając go w dowodzie.

O

$\mathcal{O}$

R

$R$

A

$A$

@Adam, ważny jest inny kwantyfikator. Myślę, że łatwiej jest przyjrzeć się negacji: czy jest możliwe, że dla prawie każdej wyroczni istnieje niejednolity przeciwnik, który może wykorzystać wyrocznię do przełamania problemu wyszukiwania?

— Kaveh

Widzę. Odpowiadałem na inne pytanie. Przepraszam za zamieszanie.

— Adam Smith,

@domotorp: Należy je teraz naprawić. (Mój najlepszy przypuszczenie dla dlaczego tak się stało jest stosowanie ponumerowanych linki zamiast in-line linki.)

$\hspace{1.05 in}$

Nie dla mojego tytułu i Tak dla ciała mojego pytania. W rzeczywistości natychmiast uogólnia się
na każdą grę wielomianową, która nie korzysta z kodu przeciwnika.

Zauważ, że będę używał dla przeciwników, zamiast , aby dopasować się do notacji Twierdzenia 2 . $C$ $A$

Załóżmy, że dla prawie wszystkich wyroczni istnieje P / poli -algorytm wyroczni taki, że nie jest bez znaczenia. $\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]$

Dla prawie wszystkich wyroczni istnieje dodatnia liczba całkowita d taka, że istnieje sekwencja obwodów o wielkości co najwyżej d + n ^d taka, że jest nieskończenie często większy niż . $\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)$

Według policzalnej addytywności istnieje dodatnia liczba całkowita d, taka że dla niepustego zbioru wyroczni istnieje sekwencja obwodów o wielkości co najwyżej d + n ^d taka, że jest nieskończenie często większy niż . $\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)$

Niech j będzie taką reklamą i niech z będzie (niekoniecznie wydajnym) algorytmem wyroczni, który
przyjmuje n jako dane wejściowe i wyjściowe najmniejszego leksykograficznie obwodu wielkości co najwyżej j + n który maksymalizuje . Przez contrapositive z Borela-Cantelli , $^{\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] \;\;\;$ dla nieskończenie wielu n.

Dla takiego 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]$

.

Niech będzie algorytmem wyroczni, który przyjmuje 2 dane wejściowe, z których jedno ma wartość , i wykonuje następujące czynności: $A$ $n$

Wybierz losowy ciąg n-bitowy . Próba [parsowania drugiego wejścia jako obwodu oracle i uruchomienia tego obwodu oracle na łańcuchu n-bit]. Jeśli to się powiedzie, a wyjście obwodu oracle spełnia R (x, y), to wyjście 1, w przeciwnym razie wyjście 0. (Zauważ, że nie jest tylko przeciwnikiem.) Dla nieskończenie wielu n, . Niech p będzie jak w Twierdzeniu 2 i ustawi $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] \:\:\:\:$
$\;\;\; 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} \:\:\:\:$ .

Według Twierdzenia 2 istnieje funkcja wyroczni taka, że z jak w tym twierdzeniu, jeślinastępnie $\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] \;\;\;$

$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] \;\;\;$ .

Dla n takich, że: $\;\;\; 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] \;\;\;$

W szczególności istnieje $\big[$ wyrocznią obwodu o rozmiarze co najwyżej j + N i zadanie o długości co najwyżej f tak, że przy tym wejściu i wstępnym próbkowaniu prawdopodobieństwo wypisania jest większe niż . Obwody Oracle o rozmiarze co najwyżej j + n mogą być reprezentowane za pomocą bitów poli (n), więc dla p jest ograniczony powyżej wielomianem in, co oznacza, że f jest również ograniczone powyżej przez wielomian w n. $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}$

Konstrukcja oznacza, że istnieją obwody oracle wielkości o wielkości co najwyżej j + n i przypisanie długości wielomianowej, tak że w przypadku uruchomienia z tym wstępnym próbkowaniem prawdopodobieństwo znalezienia obwodów rozwiązanie jest większe niż . Ponieważ takie obwody nie mogą tworzyć zapytań dłuższych niż j + n $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}$ bitów, wejścia preamplowane dłuższe niż to można zignorować, więc takie preampling może być efektywnie i doskonale symulowany za pomocą losowej wyroczni i bitów poli (n) zakodowanych na stałe. Oznacza to, że istnieją wielomianowe obwody wyroczni takie, że przy standardowej losowej wyroczni prawdopodobieństwo znalezienia rozwiązania przez obwody jest większe niż . Taką losową wyrocznię można z kolei skutecznie i doskonale symulować za pomocą zwykłych losowych bitów, więc istnieją wielomianowe probabilistyczne obwody nie- cudowne, których prawdopodobieństwo znalezienia rozwiązania jest większe niż $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)$ . Z kolei przez zakodowane losowo optyczne losowości istnieją obwody deterministyczne wielomianowe (nieprzekraczalne), których prawdopodobieństwo (powyżej wyboru x) znalezienia rozwiązania jest większe niż . Jak pokazano wcześniej w tej odpowiedzi, jest nieskończenie wiele takich n, że, $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] \;\;\;$ $\;\;\;$ więc istnieje wielomian taki, że

sekwencja, której n-ty wpis jest najmniejszy leksykograficznie
[obwód C o rozmiarze ograniczonym powyżej przez ten wielomian], który maksymalizuje $\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]$

jest algorytmem P / poli, którego prawdopodobieństwo (w stosunku do wyboru x) znalezienia rozwiązania jest niemałe.

Dlatego konsekwencje w ciele mojego pytania są zawsze aktualne.

Aby uzyskać ten sam wpływu na innych gier wielomian długości, tylko
zmienić to dowód na , aby go mają obwody wejściowe Oracle gry. $A$