patternMinor
Logical Reduction
Viewed 0 times
logicalreductionstackoverflow
Problem
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?
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?
Solution
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."
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."
Context
StackExchange Computer Science Q#37845, answer score: 4
Revisions (0)
No revisions yet.