[Solved]: Logical Reduction

Problem Detail: 

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?

Asked By : Andreas T

Answered By : Andreas T

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37845