Was kann über A nach B gesagt werden, wenn A nach C und B nach C mit bekannten Komplexitäten vorliegen?

Question

Angenommen, ich habe zwei Wertesätze $A$ Und $B$ und für jede Menge habe ich eine berechenbare Funktion von dieser Menge bis zu einer dritten Menge $C$.Nehmen wir nun an, ich möchte eine Funktion aus erstellen $A$ Zu $B$, so dass, wenn ich diese Funktion mit dem komponiere $B$ Zu $C$ Mit der oben erwähnten Funktion erhalte ich eine Funktion, die die gleichen Ergebnisse liefert wie die $A$ Zu $C$ oben erwähnte Funktion.

Wenn ich die Zeitkomplexität der beiden Funktionen kenne, die Elemente von zurückgeben $C$, erlaubt mir das, etwas über eine Funktion von zu sagen? $A$ Zu $B$ mit der angegebenen Eigenschaft?Können beispielsweise der Rechenkomplexität einer solchen Funktion irgendwelche Grenzen gesetzt werden?Können wir überhaupt sagen, ob eine solche Funktion berechenbar ist oder nicht?

Answer 1

Wir können Sets haben $A, B, C$ mit linearzeitberechenbaren Karten $f :A \zu C$ Und $g :B \zu C$ so dass es eine Karte gibt $h:A \zu B$ mit $f = g \circ h$, aber die benötigte Zeitkomplexität/Turing-Grad für $h$ ist so hoch, wie Sie möchten.

Nachweisen:Wählen Sie eine Karte $H :\Sigma^* o \Sigma^*$ Was in jedem Sinn, den Sie gewählt haben, schwierig ist.Nun lass $A = C = \Sigma^*$, Und $B = \{\langle w, H(w) angle \mid w \in \Sigma^*\}$.Lassen $f = \mathrm{id}$ Und $g = \pi_1$, d.h. $g(\langle w,u angle) = w$.Jetzt $A,B,C$ Und $f,g$ die Kriterien des Anspruchs erfüllen, und die einzige Karte $h$ das funktioniert ist $h(w) = \langle w, H(w) angle$, was im Wesentlichen so schwer ist wie $H$.

Answer 2

Sie stellen zwei Fragen, eine über Berechnungsfähigkeit und eine über die rechnerische Komplexität.Die übliche Regel ist es, eine Frage pro Post zu stellen.Ich werde die zweite Frage beantworten.Nein, unter Standard-Vermutungen könnte die rechnerische Komplexität ziemlich schlecht sein.Angenommen, $ F: A \ TO C $ wird von $ F (x)=alpha ^ x \ bmod p $ angegeben und $ g: b \ bis c $ wird von $ g (x)=beta ^ x angegeben\ BMOD P $ , wobei $ p $ eine große Primzahl ist.Dann können Sie $ f, g $ in der Polynomzeit berechnen;Aber finden Sie eine Karte $ A \ bis B $ ist so hart wie das Berechnen des diskreten Protokolls von $ \ Beta $ Basis $ \ alpha $ , das markiert ist, um hart zu sein.

Answer 3

Die öffentliche Schlüsselkryptographie basiert auf der Idee, dass die Komplexität sehr hoch gemacht werden kann.

sei ein Set der öffentlichen Tasten und b Set privater Tasten sein und die Ergebnisse der Ergebnisse der Verschlüsselung eines bestimmten einfachen Textes.Sowohl der öffentliche als auch der private Schlüssel ermöglichen es Ihnen, den verschlüsselten Text ganz einfach zu berechnen.Sie fragen, ob Sie einen öffentlichen Schlüssel erhalten haben, können Sie einen privaten Schlüssel berechnen, der dieselbe verschlüsselte Nachricht angibt.Da der Klartext dasselbe sein muss, um die gleiche verschlüsselte Nachricht zu erhalten, würde dies sofort den privaten Schlüssel für einen beliebigen öffentlichen Schlüssel geben.