I'm studying Computability and Complexity and i came out with a doubt. The Function that reduce a problem to another one is Turing-Computable. I was wondering if its even a one-to-one function ( a correspondence) since looking,for example, to the Vertex-Cover -> Independent Set reduction i cannot see where an instance of one problem is not in correspondece with another instance of the other one.
Thank you
No, there is not a one-to-one correspondence. If you reduce problem A to problem B, for example in polynomial time (A <=_pol B), that means that you can solve problem A with the help of a solution to problem B. But it is possible that there is an input for problem B you cannot solve with a solution to A. Also the reduction function could map multiple inputs for problem A to a single input for problem B.
Take for example the reduction of Clique(G,k) to SubgraphIsomorphism(G,H): Clique <=_pol SubgraphIsomorphism. A clique is only a special subgraph H you can construct in time polynomially in k. But to be able to solve Clique(G,k) wont help you to find arbitrary subgraphs H in G. Thus, not every input for SubgraphIsomorphism corresponds to an input for Clique. This reduction merely shows that SubgraphIsomorphism is at least as hard as Clique.