Reducing one computable problem to another by providing an algorithm which trans

Question

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?

Explanation / Answer

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 ?(x,y)?

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.