A question about domains in Karp reductions

Question

A basic question or request for clarification regarding Karp reducibility:

Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote the set of all functions from $\Sigma^*$ into $\Sigma^*$ that are computable in polynomial time. According to Karp, a language $L$ is reducible to a language $M$, also denoted $L \leq_K M$, if there is a function $f \in \Pi$ such that $f(x) \in M \Leftrightarrow x \in L$.

For many problems, however, we are interested in the difficulty of determining membership in subsets of domains other than $\Sigma^*$. To address this, Karp briefly discusses encodings: Given a domain $D$, there is often a natural "one-one" encoding, $e: D \rightarrow \Sigma^*$. He then says that given a set $T \subset D$, $T$ is recognizable in polynomial time if $e(T) \in \mathcal{P}$. But don't we, in practice, typically consider $T$ to be recognizable in polynomial time if, for any $x \in D$, we can determine whether $x \in T$ in polynomial time? On the face of it, this doesn't seem to be the same as Karp's definition, since there is no guarantee that $e(D) = \Sigma^*$.

Similarly, according to Karp, $T \leq_K U$ where $T \subset D$ and $U \subset D'$ if $e(T) \leq_K e'(U)$ where $e: D \rightarrow \Sigma^*$ and $e': D' \rightarrow \Sigma^*$. However, when we are actually proving $T \leq_K U$ for some real $T$, $U$, $D$, and $D'$, don't we frequently just define an $f: D \rightarrow D'$ computable in polynomial time, confirm that $f(x) \in D'$ for any $x \in D$, and show that $f(x) \in U \Leftrightarrow x \in T$ for any $x \in D$? Again, this doesn't seem to be the same thing as Karp's definition if $e(D) \neq \Sigma^*$.

What am I missing?

Answer 1

Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can recover $G$ and $k$ in polynomial time. The language $L$ consists of all encodings $e(G,k)$ of graphs $G$ containing a vertex cover of size $k$. If a string is not in the range of $e$, it is not in $L$.

Now suppose that you have a reduction $f$ from the domain $D$ of vertex cover to the domain $D'$ of SAT, and let $e\colon D \to \Sigma^*$ and $e'\colon D' \to \Sigma^*$ be encodings of these domains. We can construct a reduction $g$ from the language $L \subseteq \Sigma^*$ of vertex cover to the language $L' \subseteq \Sigma^*$ of SAT as follows. Given a string $w \in \Sigma^*$, we first check whether it is in the range of $e$. If not, we output some fixed string not in $L$' If it is, we output $e'(f(e^{-1}(w)))$; that is, we decode $w$, apply $f$, and then encode the result.

Most of the time, such encoding details can be ignored. This is the case since we're working in a computation model which is strong enough to be oblivious to such matters. This is why we usually don't bother with these issues too much.