# A question about domains in Karp reductions

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?

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.
• This is helpful. Thanks. However, I admit I'm not sure how to reliably come up with injective encodings that allow (i) and (ii). For graphs $G = (V,E)$, this encoding is immediate from the adjacency matrix. But for one-dimensional integer arrays, just converting each integer to binary leads to ambiguous strings (is 101 [1,0,1] or [2,1] or [5]?). We might instead use a scheme like Gödel numbering to encode delimiters, but a polynomial-time algorithm for integer factorization has not yet been found. So how can we proceed? – SapereAude Feb 18 at 12:47
• Why not encode a one-dimensional integer array as $[1,0,1]$? You can use the alphabet $0123456789[,]$. If you wish, you can convert this alphabet to binary. – Yuval Filmus Feb 18 at 14:24
• Because I don't know of a way to convert the alphabet you gave to binary so that the encoding, $e: D \rightarrow \Sigma^*$, both is one-to-one and avoids a requirement to factor large integers. For example, if we map $[$ to $1010$, $,$ to $1011$, and $]$ to $1100$, then $e([1,0,1]) = 1010110110101111100$, but so does $e([54,1])$ and $e([1751])$. – SapereAude Feb 18 at 18:02