Apakah ada kelas fungsi yang membutuhkan sumber daya yang berbeda terbukti untuk menghitung versus menghitung kebalikannya?

Mohon maaf sebelumnya jika pertanyaan ini terlalu sederhana.

Pada dasarnya, yang ingin saya ketahui adalah jika ada fungsi $f(x)$ dengan properti berikut:

Ambil $f_n(x)$ menjadi $f(x)$ saat domain dan kode domain dibatasi untuk string $n$ bit. Kemudian

1. $f_n(x)$ bersifat injeksi
2. $f_n(x)$ bersifat surjektif
3. $f_n(x)$ membutuhkan sumber daya yang sangat sedikit (baik ruang / waktu / kedalaman rangkaian / jumlah gerbang) untuk dihitung dalam beberapa model yang masuk akal daripada$f^{-1}_n(y)$ , di mana$y=f_n(x)$ .
4. Perbedaan sumber daya untuk skala $f_n(x)$ vs $f^{-1}(y)$ karena beberapa fungsi $n$ .

Saya dapat memberikan contoh-contoh di mana fungsi tersebut bersifat surjektif atau injeksi, tetapi tidak keduanya kecuali saya menggunakan model komputasi yang dibuat-buat. Jika saya memilih model komputasi yang memungkinkan pergeseran kiri dalam satuan waktu pada beberapa cincin, tetapi bukan pergeseran kanan, maka tentu saja mungkin untuk menghasilkan linear over head (atau lebih tinggi jika Anda menganggap permutasi yang lebih rumit sebagai primitif) . Untuk alasan ini saya hanya tertarik pada model yang masuk akal, yang saya maksudkan kebanyakan mesin Turing atau sirkuit NAND atau serupa.

Jelas ini pasti benar jika , tetapi akan terlihat bahwa ini juga mungkin jika P = N P , dan dengan demikian tidak berarti memutuskan pertanyaan itu.$P\neq NP$$P=NP$

Sangat mungkin bahwa pertanyaan ini memiliki jawaban yang jelas atau hambatan yang jelas untuk menjawab yang telah saya lewatkan.

Saya diminta untuk mengirim ulang komentar saya. Saya menunjukkan makalah ini oleh Hastad, yang menunjukkan bahwa ada permutasi dalam yang P-sulit untuk dibalik:$NC^0$

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Untuk sirkuit boolean lebih dari basis biner penuh (dengan ukuran kompleksitas menjadi jumlah gerbang dalam sirkuit minimal) rasio yang paling dikenal untuk permutasi C ( f - 1$C(f)$. Sejauh yang saya tahu, konstanta terbaik diperoleh dalamkarya inioleh Hiltgen dan sama dengan 2.$\frac{C(f^{-1})}{C(f)} = const$

Edit. Ketika Anda ingin rasio meningkat ketika tumbuh, ini tidak menjawab pertanyaan Anda. Namun, untuk sirkuit boolean atas basis biner penuh tidak ada yang lebih baik diketahui.$n$

Pertama-tama, saya ingin menunjukkan surjectivity yang tidak didefinisikan dengan baik tanpa terlebih dahulu mendefinisikan kodomain fungsi. Jadi, dalam uraian saya di bawah ini, saya akan secara eksplisit merujuk pada kode domain yang fungsinya bersifat surjektif.

Baik fungsi logaritma diskrit atau RSA adalah permutasi yang diduga sulit untuk dibalik. Di bawah ini, saya akan menjelaskan fungsi diskrit-logaritma.

Misalkan menjadi n- bit prime, dan g menjadi generator dari grup multiplikasi Z ∗ p n . Tentukan f n : Z p n → Z p n sebagai f n ( x ) = g $p_n$$n$$g$$\mathbb{Z}_{p_n}^*$$f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ .$f_n(x) = g^x \pmod{p_n}$

$f_n$$\mathbb{Z}_{p_n}$$f_n$