Gibt es Klassen von Funktionen, deren Berechnung nachweislich andere Ressourcen erfordert als deren Umkehrung?

Entschuldigung im Voraus, wenn diese Frage zu einfach ist.

Grundsätzlich möchte ich wissen, ob es Funktionen $f(x)$ mit den folgenden Eigenschaften gibt:

Nehmen Sie als wenn die Domäne und die Codomäne auf Bit-Zeichenfolgen beschränkt sind. Dannf ( x ) $f_n(x)$$f(x)$$n$

1. $f_n(x)$ ist injektiv
2. $f_n(x)$ ist surjektiv
3. $f_n(x)$ benötigt streng weniger Ressourcen (entweder Raum / Zeit / Schaltkreistiefe / Anzahl der Gatter), um unter einem vernünftigen Modell zu berechnen als , wobei .y = f n ( x $f^{-1}_n(y)$$y=f_n(x)$
4. Die Ressourcendifferenz für vs skaliert als eine streng zunehmende Funktion von .f - 1 ( y ) $f_n(x)$$f^{-1}(y)$$n$

Ich kann Beispiele nennen, bei denen die Funktion entweder surjektiv oder injektiv ist, aber nicht beides, es sei denn, ich greife auf ein erfundenes Rechenmodell zurück. Wenn ich ein Rechenmodell wähle, das Linksverschiebungen in der Zeiteinheit für einen Ring zulässt, aber keine Rechtsverschiebungen, ist es natürlich möglich, einen linearen Overhead (oder einen höheren, wenn Sie eine kompliziertere Permutation als Grundelement betrachten) zu erstellen. . Aus diesem Grund interessiere ich mich nur für vernünftige Modelle, womit ich meistens Turingmaschinen oder NAND-Schaltungen oder ähnliches meine.

Offensichtlich muss dies wahr sein, wenn , aber es scheint, dass dies auch möglich ist, wenn , und sollte daher nicht zu einer Entscheidung dieser Frage führen.P = N $P\neq NP$$P=NP$

Es ist durchaus möglich, dass diese Frage eine offensichtliche Antwort hat oder ein offensichtliches Hindernis für die Beantwortung, das ich verpasst habe.

Ich wurde gebeten, meinen Kommentar erneut zu veröffentlichen. Ich habe auf dieses Papier von Hastad hingewiesen, das zeigt, dass es in Permutationen gibt , die P-schwer zu invertieren sind:$NC^0$

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

Für Boolesche Schaltungen über die volle Binärbasis (wobei das Komplexitätsmaß die Anzahl der Gatter in einer Minimalschaltung ist) ist das bekannteste Verhältnis für Permutationen C ( f - 1$C(f)$. Soweit ich weiß, wurde die beste Konstante indieser Arbeitvon Hiltgen erhalten und ist gleich 2.$\frac{C(f^{-1})}{C(f)} = const$

Bearbeiten. Da Sie möchten, dass sich das Verhältnis erhöht, wenn wächst, beantwortet dies Ihre Frage nicht. Für Boolesche Schaltungen über die volle Binärbasis ist jedoch nichts Besseres bekannt.$n$

Zunächst wollte ich darauf hinweisen, dass die Surjektivität nicht gut definiert ist, ohne zuerst die Codomäne der Funktion zu definieren. Daher werde ich in meiner folgenden Beschreibung explizit auf die Codomäne verweisen, über die die Funktion surjektiv ist.

Sowohl der diskrete Logarithmus als auch die RSA- Funktionen sind Permutationen, von denen angenommen wird, dass sie schwer zu invertieren sind. Im Folgenden werde ich die Funktion des diskreten Logarithmus beschreiben.

Sei eine n- Bit-Primzahl und g ein Generator der multiplikativen Gruppe Z ∗ p n . Definieren f n : Z p n → Z p n wie 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}$

Dann ist eine Funktion, deren Eigenschaften wie in Ihrer Frage angegeben sind: Sie ist sowohl injektiv als auch surjektiv (über die Codomäne Z p n ), sie ist in Polynomzeit berechenbar, es wird jedoch vermutet, dass kein effizienter Algorithmus f n weiter invertieren kann durchschnittlich.$f_n$$\mathbb{Z}_{p_n}$$f_n$