Dados A a C y B a C con complejidades conocidas, ¿qué se puede decir acerca de A a B?

Question

Digamos que tengo dos conjuntos de valores. $A$ y $B$ y para cada conjunto tengo una función computable de ese conjunto a un tercer conjunto $C$.Ahora supongamos que quiero construir una función a partir de $A$ a $B$, de modo que si compongo esa función con el $B$ a $C$ función mencionada anteriormente obtengo una función que produce los mismos resultados que la $A$ a $C$ función mencionada anteriormente.

Si conozco la complejidad temporal de las dos funciones que devuelven elementos de $C$, ¿eso me permite decir algo sobre una función de $A$ a $B$ con la propiedad especificada?Por ejemplo, ¿se pueden poner límites a la complejidad computacional de dicha función?¿Podemos siquiera decir si tal función es computable o no?

Answer 1

Podemos tener conjuntos $A, B, C$ con mapas computables en tiempo lineal $f:A \a C$ y $g :B \a C$ tal que existe un mapa $h:A \a B$ con $f = g \circh$, pero la complejidad del tiempo necesaria/grado de Turing para $h$ es tan alto como quieras.

Prueba:Elige un mapa $H :\Sigma^* \a \Sigma^*$ lo cual es difícil en cualquier sentido que hayas elegido.Ahora deja $A = C = \Sigma^*$, y $B = \{\langle w, H(w) angle \mid w \in \Sigma^*\}$.Dejar $f = \mathrm{id}$ y $g = \pi_1$, es decir. $g(\langle w,u angle) = w$.Ahora $A,B,C$ y $f,g$ cumplir con los criterios de la reclamación, y el único mapa $h$ eso funciona es $h(w) = \langle w, H(w) angle$, que es esencialmente tan difícil como $h$.

Answer 2

Estás haciendo dos preguntas, una sobre la computabilidad y una sobre la complejidad computacional.La regla habitual es hacer una pregunta por publicación.Responderé a la segunda pregunta.No, bajo conjeturas estándar, la complejidad computacional podría ser bastante mala.Supongamos que $ F: A \ a C $ se le da por $ f (x)=alfa ^ x \ bmod p $ y $ g: b \ a c $ se le da por $ g (x)=beta ^ x\ bmod p $ , donde $ p $ es un gran número primo.Luego, puede calcular $ f, G $ en tiempo polinomial;Pero encontrar un mapa $ A \ a b $ es tan difícil como computar el registro discreto de $ \ beta $ A base $ \ alfa $ , que se conjeture para ser difícil.

Answer 3

La criptografía de la clave pública se basa en la idea de que la complejidad puede ser muy alta.

Sea un conjunto de claves públicas, y B es el conjunto de claves privadas, y c El conjunto de resultados de cifrar algún texto plano fijo.Tanto la clave pública como la privada le permiten calcular el texto encriptado con bastante facilidad.Pero usted está preguntando si se le da una clave pública, puede calcular una clave privada con el mismo mensaje encriptado.Dado que el texto plano debe ser el mismo para obtener el mismo mensaje encriptado, esto le daría inmediatamente la clave privada a cualquier clave pública.