Quali sono conosciute riduzioni da 3sat a 2sat?

Question

C'è un modo per convertire una formula da 3sat in una formula 2sat equisa soddisfacente? Ogni metodo è interessante, anche quelli che crescono esponenzialmente. (Quindi se, ad esempio, la mia formula 3SAT ha 16 variabili e 32 clausole, una formula a 2sat trasformata avrebbe 2ˆ16 variabili e / o clausole 2ˆ32)

Un esempio di una formula 3sat che vorrei convertire è:

A xor b xor c

O lo stesso in CNF:

(A o B o C) e (A o! B o! C) e (! A o! B o C) e (! A o B o! C)