1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – SapereAude Feb 18 at 12:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 18 at 14:24
  • $\begingroup$ 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])$. $\endgroup$ – SapereAude Feb 18 at 18:02
  • 1
    $\begingroup$ You need to be more imaginative. My alphabet has size 13. You can encode each letter using 4 bits. If you see one of the 3 remaining combinations, reject the string. $\endgroup$ – Yuval Filmus Feb 18 at 19:37
  • $\begingroup$ Well, I'm embarrassed. I can't believe I didn't see this with everything I tried. Thanks. $\endgroup$ – SapereAude Feb 18 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.