Apa yang diketahui tentang mendasarkan fungsi satu arah pada asumsi

Apakah ada hasil ketidakmungkinan bersyarat atau pertanyaannya benar-benar terbuka?

Kita tidak bisa berharap untuk membuktikan hasil ketidakmungkinan umum karena jika fungsi satu arah ada (dan kami percaya mereka melakukannya), maka secara khusus mengikuti bahwa pernyataan "Jika maka fungsi satu arah ada" adalah benar.$P \ne NP$

Namun, kita dapat membuktikan bahwa teknik pembuktian tertentu terlalu lemah untuk membuktikan pernyataan itu. Secara khusus, makalah Akavia, Goldreich, Goldwasser, dan Moshkovitz berikut ini membuktikan bahwa pernyataan ini tidak dapat dibuktikan dengan pengurangan kotak hitam tertentu (dikondisikan pada asumsi yang masuk akal):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html

Jika yang Anda maksud adalah jenis kriptografi dari fungsi satu arah (mis. Kasus rata-rata sulit dibalik), maka jawaban Or Meir luar biasa. Tetapi untuk gagasan sedikit lebih mudah dari fungsi satu arah kasus terburuk - yaitu, fungsi injeksi yang dapat dihitung dalam waktu polinomial, tetapi di mana tidak ada algoritma polinomial-waktu deterministik g sedemikian sehingga f ( g ( y ) ) = y untuk semua y pada gambar f dan g ( y ) = 0 sebaliknya - ada jawaban yang lebih tepat. Yaitu, fungsi satu arah kasus terburuk ada$f$$g$$f(g(y)) = y$$y$ $f$$g(y)=0$jika dan hanya jika .$\mathsf{P} \neq \mathsf{UP}$

Jadi untuk kasus terburuk satu arah fungsi, pertanyaan Anda pada dasarnya bermuara pada hubungan antara dan N P . Hubungan ini pada dasarnya terbuka lebar, dan ada nubuat di kedua arah. Beberapa hubungan untuk pertanyaan terkait diketahui - yaitu, Valiant-Vazirani ( N P ⊆ R P P r o m i s e U P ) dan Hemaspaandra-Naik-Ogihara-Selman ( N P M V ⊆ c N P S V menyiratkan P $\mathsf{UP}$$\mathsf{NP}$$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$$\mathsf{PH}$runtuh) - tapi aku tidak mengetahui adanya langsung hubungan, tanpa syarat yang berkaitan dengan dan U P tepat.$\mathsf{NP}$$\mathsf{UP}$