# complexity theory – An elementary question about domain 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?