L-reduction

Example

← Previous revision Revision as of 13:14, 5 May 2026 Line 22: Line 22:

<math>f(\varphi) := \bigwedge_{i=1}^m (\ell_i^1 \land \ell_i^2 \land \ell_i^3 \land \ell_i^4 \land (\bar \ell_i^1 \lor \bar \ell_i^2) \land (\bar \ell_i^1 \lor \bar \ell_i^3) \land (\bar \ell_i^2 \lor \bar \ell_i^3) \land (\ell_i^1 \lor \bar \ell_i^3) \land ( \ell_i^2 \lor \bar \ell_i^4)\land (\bar \ell_i^3 \lor \bar \ell_i^4) </math> where <math>\ell_i^4</math> is a new variable. <math>f(\varphi) := \bigwedge_{i=1}^m (\ell_i^1 \land \ell_i^2 \land \ell_i^3 \land \ell_i^4 \land (\bar \ell_i^1 \lor \bar \ell_i^2) \land (\bar \ell_i^1 \lor \bar \ell_i^3) \land (\bar \ell_i^2 \lor \bar \ell_i^3) \land (\ell_i^1 \lor \bar \ell_i^3) \land ( \ell_i^2 \lor \bar \ell_i^4)\land (\bar \ell_i^3 \lor \bar \ell_i^4) </math> where <math>\ell_i^4</math> is a new variable.
The function <math>g</math> of our L-reduction is defined as follows. Given an assignment <math>\nu</math> for <math>f(\varphi)</math>, we define <math>g(\nu)</math> to be the assignment <math>\nu</math> restricted to variables in <math>\varphi</math> (i.e. we just ignore the truths of the variables <math>\ell_i^4</math>).

==Properties== ==Properties==