Quali sono conosciute riduzioni da 3sat a 2sat?
-
05-11-2019 - |
Domanda
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)
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange