Compte tenu de C, et B à C avec des complexités connues, qu'est-ce qui peut être dit sur A à B?

Question

dire que j'ai deux séries de valeurs $ a $ a $ et $ B $ et pour chaque ensemble i avoir une fonction calculable de celle définie sur un troisième jeu $ C $ . Maintenant supposons que je souhaite construire une fonction de $ a $ à $ b $ , tel que si je composez cette fonction avec la $ B $ to $ C $ fonction mentionnée ci-dessus, je reçois une fonction qui produit le mêmes résultats que la $ A $ à $ C $ fonction mentionnée ci-dessus.

Si je connais la complexité temporelle des deux fonctions qui renvoient des éléments de $ C $ , cela me permettez-moi de dire quelque chose sur une fonction de $ A $ A $ à $ B $ avec la propriété spécifiée? Par exemple, des limites peuvent-elles être placées sur la complexité de calcul d'une telle fonction? Pouvons-nous même dire si une telle fonction est calculable ou non?

Answer 1

Nous pouvons avoir des ensembles $ A, B, C $ avec des cartes calculables de temps linéaire $ F: A \ to C $ et $ g: b \ to c d $ de telle sorte qu'il existe une carte $ h: a \ à B $ avec $ f= g \ circr $ , mais la complexité du temps nécessaire / degré de durcissement pour $ h $ est aussi élevé que vous le souhaitez.

Preuve: Choisissez une carte $ H: \ SIGMA ^ * \ to \ SIGMA ^ * $ Quel est difficile dans le sens de votre choix. Maintenant, laissez $ a= c=sigma ^ * $ et $ b={\ langle w, h (w ) \ RANGER \ MID W \ IN \ SIGMA ^ * \ ^} $ . Laissez $ f=mathrm {id} $ et $ g=pi_1 $ , c'est-à-dire $ g (\ lambeaux w, u \ rangle)= w $ . Maintenant $ a, b, c $ et $ f, g $ répondez aux critères de la réclamation et La seule carte $ h $ qui fonctionne est $ h (w)=lambeaux w, h (w) \ rât $ $ , qui est essentiellement aussi difficile que $ h $ .

Answer 2

Vous posez deux questions, une sur la calculabilité et une complexité de calcul.La règle habituelle est de poser une question par post.Je vais répondre à la deuxième question.Non, sous des conjectures standard, la complexité de calcul pourrait être assez mauvaise.Supposons $ F: A \ to C $ est donné par $ f (x)=alpha ^ x \ bmod p $ et $ g: b \ to c d $ est donné par $ g (x)=beta ^ x\ bmod p $ , où $ p $ est un grand nombre de nombres premiers.Alors vous pouvez calculer $ f, g $ en temps polynomial;Mais trouver une carte $ a \ to b $ est aussi difficile que calculer le journal discrète de $ \ beta $ Pour fonder $ \ alpha $ , qui est conjecturé pour être dur.

Answer 3

La cryptographie de clé publique est basée sur l'idée que la complexité peut être rendue très élevée.

Soit A l'ensemble des touches publiques et B Soyez l'ensemble des clés privées et c L'ensemble des résultats de crypter du texte brut.La clé publique et privée vous permet de calculer le texte crypté assez facilement.Mais vous demandez si vous avez reçu une clé publique, vous pouvez calculer une clé privée donnant au même message crypté.Étant donné que le texte brut doit être pareil pour obtenir le même message crypté, cela vous donnerait immédiatement la clé privée à une clé publique.