Dada a para C, e de B para C com o conhecido complexidades, o que pode ser dito a respeito de a para B?

Question

Digamos que eu tenha dois conjuntos de valores $A$ e $B$ e para cada conjunto de eu ter uma função computável do que definir um terceiro conjunto $C$.Agora, suponha que eu quero construir uma função de $A$ para $B$, de tal forma que se eu compor essa função com o $B$ para $C$ a função acima mencionadas, recebo uma função que produz os mesmos resultados como o $A$ para $C$ função mencionada acima.

Se eu sei que o tempo-a complexidade das duas funções que retornam elementos de $C$, não que me permitem dizer qualquer coisa sobre uma função de $A$ para $B$ com a propriedade especificada?Por exemplo, pode quaisquer limites sejam colocados sobre a complexidade computacional de uma tal função?Podemos mesmo dizer que se uma função é computável ou não?

Answer 1

Podemos ter conjuntos de $A, B, C$ com linear de tempo computável mapas $f :A \C$ e $g :B \C$ de tal forma que existe um mapa $h :A o B$ com $f = g \circ h$, mas o tempo necessário complexidade/Turing grau de $h$ é tão alto quanto você quiser.

Prova:Escolha um mapa $H :\Sigma^* \a \Sigma^*$ o que é difícil em qualquer sentido que você escolheu.Agora vamos $A = C = \Sigma^*$, e $B = \{\langle w, H(w) angle \mid w \in \Sigma^*\}$.Deixe $f = \mathrm{id}$ e $g = \pi_1$, i.é. $g(\langle w,u angle) = w$.Agora $A,B,C$ e $f,g$ atender os critérios da reclamação, e o único mapa $h$ o que funciona é $h(w) = \langle w, H(w) angle$, que é essencialmente tão duro como $H$.

Answer 2

Você está fazendo duas perguntas, uma sobre a computabilidade e uma sobre a complexidade computacional.A regra usual é fazer uma pergunta por postagem.Eu responderei a segunda pergunta.Não, sob conjeturas padrão, a complexidade computacional pode ser bastante ruim.Suponha $ f: A \ a C $ é dado por $ f (x)=alfa ^ x \ bmod p $ e $ g: B \ to C $ é dado por $ g (x)=beta ^ x\ bmod P $ , onde $ P $ é um grande número primo.Então você pode calcular $ f, g $ no tempo polinomial;Mas encontrar um mapa $ a \ to b $ é tão difícil quanto calcular o log discreto da $ \ beta $ para base $ \ alfa $ , que é conjeturado para ser difícil.

Answer 3

Criptografia de chave pública baseia-se na ideia de que a complexidade pode ser muito alta.

Deixe um conjunto de chaves públicas, e B ser o conjunto de chaves privadas e c o conjunto de resultados de criptografar algum texto simples fixo.Tecla pública e privada permitem calcular o texto criptografado com bastante facilidade.Mas você está perguntando se dada uma chave pública, você pode calcular uma chave privada dando a mesma mensagem criptografada.Como o texto simples deve ser o mesmo para obter a mesma mensagem criptografada, isso imediatamente lhe daria a chave privada para qualquer chave pública.