3
$\begingroup$

Reducing one computable problem to another by providing an algorithm which transforms an instance of one problem to one of the other (and limiting the time or space of that algorithm) is clear to me. However, I fail to understand how reductions via logic work, e.g. a reduction in FO. My biggest problem is that the structures themselves would have to be encoded as a structure to be accessible to such a reduction. Could someone provide me with an example of a reduction in logic?

If it is not clear what I am talking about, maybe an example helps: Reducing SAT to 3SAT can be done in PTIME, so there should be an LFP reduction as well. How would the formula in LFP look like which performs the transformation of an instance of SAT to an instance of 3SAT?

$\endgroup$
3
$\begingroup$

Logical reductions work in essentially the same way as computational ones. In computational reductions, you show how to compute an instance of the target problem; in logical reductions, you show how to define it. In practical terms, that's often almost the same thing since, for example, you reduce clique to independent set just by saying "Swap edges and non-edges", rather than defining an algorithm that actually does that.

When you're dealing super-formally with computational reductions, your input is normally assumed to be a string in some fixed alphabet, though one often just assumes it to be "a graph" or "a Boolean formula". The details of the encoding of such objects as strings are usually not important.

Typically, when you're dealing with logical reductions, your input is assumed to be a relational structure of some appropriate vocabulary, rather than a string. (Strings can, themselves, be represented as relational structures, should you need to do that.) You typically have to be very precise about what the vocabulary is since, otherwise, it's impossible to write formulae. So, for example, to reduce clique to independent set, you'd say that your graph is defined as a binary relation $E$, denoting the edges, and the edge relation of the new graph is defined by the formula $\phi(x,y)\equiv \neg E(x,y)$.

As for writing an LFP formula to reduce SAT to 3SAT, that's, er, left as an exercise to the reader. I'd be surprised if one could formally describe such a reduction in less than a couple of pages.

That's a bit of a cop-out, I admit, as was choosing a near-trivial example. The first obvious difficulty in more complicated examples is producing an instance $J$ with a larger universe than the original instance $I$. To deal with this, elements of the universe of $J$ are represented by tuples of $I$-elements. Writing $n$ for the size of $I$'s universe, the simple case of needing $J$ to have $n^k$ elements is dealt with by using $k$-tuples. For more complicated cases, there are a variety of techniques. If you have a linear order available, you can restrict components of the tuples using that (e.g., "the second element of the pair must be one of the first four elements of the order" gives you a universe of size $4n$). Any definable set can be used in a similar way. Another trick is to produce $J$ plus a lot of garbage and somehow define away the garbage. For example, you might define $J$ in a way that causes it to have multiple garbage components but be able to say "I'm only interested in the component that contains this special vertex."

$\endgroup$
  • $\begingroup$ I see how your example for Clique and IndependentSet makes sense by using a formula to define every relation of the target structure. However, that only works if you assume that the domain of both structures is the same. What would a transformation look like if this is not the case? For example, you want to transform a graph (V,E) into the same graph which is just two disconnected copies of the first one. $\endgroup$ – Andreas T Feb 1 '15 at 20:49
  • $\begingroup$ @AndreasT If you need a larger domain, you can use tuples of vertices in the original structure to represent single vertices in the new one. For example, you can define a graph on $n^2$ vertices relative to one on $n$ vertices by saying that each pair of vertices in the old graph stands for a single vertex in the new graph. Then, the binary edge relation on the new graph looks like a 4-ary relation on the original vertex set. (There's a name for this technique but I can't remember it, right now.) $\endgroup$ – David Richerby Feb 1 '15 at 20:54
  • $\begingroup$ My answer to this question covers some similar ideas and might be helpful. (I'm certainly not proposing it as an answer to this question, mind you.) $\endgroup$ – David Richerby Feb 1 '15 at 20:58
  • $\begingroup$ Well, the example you gave is one of the few which does not really help me with my question. For graphs which have exactly $n^k$ vertices, for some k, using tuples works. But what about all the other cases, for example if you want to double the number of vertices? $\endgroup$ – Andreas T Feb 1 '15 at 21:33
  • $\begingroup$ @AndreasT You're right, my example was too trivial to be really useful. Does the edited answer help? (I didn't change anything outside the added paragraph.) $\endgroup$ – David Richerby Feb 1 '15 at 23:30
1
$\begingroup$

David Richerby already answered the question partially but I had the chance to ask the professor for logic at my university today. He showed me one kind of logical reduction.

Given two problems, $X$ and $Y$, to reduce $X \leq_\text{FO} Y$: Let $\tau$ be the signature of the instances in $X$ and $\sigma$ the signature of instances in $Y$. Let $\mathfrak{A} = (A, \tau)$ be an instance of $X$. The FO-reduction from $X$ to $Y$ is defined as a set of $\text{FO}(\tau)$-formulas $\delta(\overline{x}), \left( \varphi_i(\overline{x}) \right)_{i \in \sigma}$, where $\overline{x}$ are tuples of variables of any fixed size.

Then $\mathfrak{B} = (B, \sigma)$ is defined as $B = \{\overline{a} \in A \mid \mathfrak{A} \models \delta(\overline{a})\}$ and for all $i \in \sigma$, $i^\mathfrak{B} = \{\overline{a} \in A \mid \mathfrak{A} \models \varphi_i(\overline{a})\}$.

One advantage of this reduction is that if it is correct, one can also use the transformation to find a formula which decides $X$ (assuming one has a formula $\psi$ for $Y$). This is done by relativizing the quantifiers ($\exists x \vartheta(x)$ is replaced by $\exists \overline{x} \vartheta(\overline{x}) \land \delta(\overline{x})$) and symbols from $\sigma$.

$\endgroup$

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.