Bisakah peramalan acak mengubah masalah TFNP yang sangat sulit rata-rata?

Saya telah memikirkan pertanyaan berikut pada
berbagai waktu sejak saya melihat pertanyaan tentang Kriptografi ini .

Pertanyaan

Biarkan menjadi hubungan TFNP . Dapatkah oracle acak membantu P / poli untuk memecahkan dengan probabilitas yang tidak dapat diabaikan? Lebih formal, $R$
$R$ $\newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}}$

Apakah

untuk semua P / poly algoritma , adalah diabaikan $A$ $\Pr_x [R(x, A(x))]$

tentu menyiratkan itu

untuk hampir semua o racles , untuk semua P / poli oracle-algoritma , diabaikan $\O$ $A$ $\Pr_x [R(x, A^\O(x))]$

Formulasi alternatif

Seperangkat nubuat yang relevan adalah $G_{\delta\sigma}$ (sehingga dapat diukur), sehingga dengan mengambil kontrapositif dan menerapkan hukum nol-satu Kolmogorov , formulasi berikut ini setara dengan yang asli.

Apakah

untuk hampir semua o rash , terdapat algoritma P / poly oracle- sehingga tidak dapat diabaikan $\O$
$A$ $\Pr_x [R(x,A^\O(x))]$

tentu menyiratkan itu

ada algoritma P / poly sehingga tidak dapat diabaikan $A$ $\Pr_x [R(x,A(x))]$

Kasus seragam

Ini bukti untuk versi seragam :

Hanya ada banyak-banyak PPT oracle-algoritma, sehingga dengan aditivitas yang dapat dihitung dari null [ideal] [8], ada algoritma PPT sedemikian rupa sehingga untuk seperangkat oracle yang bukan nol , tidak dapat diabaikan. Biarkan menjadi seperti algoritma-oracle. $A$ $\O$
$\Pr_x [R(x,A^\O(x))]$ $B$

Demikian pula, misalkan menjadi bilangan bulat positif sehingga untuk seperangkat orakel non-nol , adalah tak terhingga-sering setidaknya , di mana adalah panjang input. Oleh Contrapositive Borel-Cantelli , $c$ $\O$
$\Pr_x[R(x,B^\O(x))]$ $n^{-c}$ $n$
tidak terbatas. $\sum_{n=0}^{\infty} \Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))] \right]$

Dengan uji perbandingan , sering kali . $\Pr_{\O} \left[ n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x)) \right] \geq n^{-2}$

Misalkan adalah algoritma PPT yang [mensimulasikan oracle] [12] dan menjalankan dengan simulasi-oracle tersebut. $S$ $B$

Fix dan membiarkan adalah himpunan firman sehingga . $n$ $\Good$ $\O$ $n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$

Jika tidak null maka $\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}$

Karena seringkali tak terhingga, tidak dapat diabaikan. $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ $\Pr_x[R(x,S(x))]$

Oleh karena itu versi seragam berlaku. Buktinya secara kritis menggunakan fakta bahwa
hanya ada banyak algoritma PPT oracle. Gagasan ini tidak berfungsi dalam kasus yang
tidak seragam, karena ada banyak algoritma kontinum-P / poli oracle.

cr.crypto-security relativization advice-and-nonuniformity search-problem random-oracles Komunitas
sumber

O

$\mathcal{O}$

R

$R$

A

$A$

A

$A$

A

$A$

A

$A$

O

$\mathcal{O}$

R

$R$

A

$A$

@ Adam, ada kuantifier lain yang penting. Saya pikir lebih mudah untuk melihat negasi: apakah mungkin bahwa untuk hampir setiap oracle ada musuh yang tidak seragam yang dapat menggunakan oracle untuk memecahkan masalah pencarian?

Kaveh

Saya melihat. Saya menjawab pertanyaan yang berbeda. Maaf bila membingungkan.

Adam Smith

@domotorp: Mereka harus diperbaiki sekarang. (Tebakan terbaik saya mengapa itu terjadi adalah

$\hspace{1.05 in}$ menggunakan link bernomor daripada link in-line).

Tidak untuk judul saya, dan Ya untuk tubuh pertanyaan saya. Ini sebenarnya menggeneralisasi segera
ke setiap gim panjang polinomial yang tidak menggunakan kode musuh.

$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)$

Biarkan j menjadi iklan seperti itu, dan biarkan z menjadi algoritma oracle (tidak-harus-efisien) yang
menggunakan n sebagai input dan menghasilkan sirkuit ukuran oracle paling leksikografis paling besar j + n $^{\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] \;\;\;$ untuk banyak sekali n.

Untuk n seperti itu,

$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] \:\:\:\:$ .
Biarkan p menjadi seperti di Teorema 2 , dan atur $\;\;\; 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] \;\;\;$ kemudian

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

Untuk n seperti itu $\;\;\; 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] \;\;\;$ , $\;\;\;$ jadi ada polinomial sedemikian rupa

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

adalah algoritma P / poly yang probabilitasnya (atas pilihan x) untuk menemukan solusi tidak dapat diabaikan.

Karena itu implikasinya ada dalam tubuh pertanyaan saya.

$A$

sumber

Bisakah peramalan acak mengubah masalah TFNP yang sangat sulit rata-rata?

Pertanyaan

Formulasi alternatif

Kasus seragam

Jawaban: