Struttura generale delle soluzioni ai circuiti a 3 sacchetti
-
05-11-2019 - |
Domanda
Alcune forme speciali del problema SAT hanno set di soluzioni di una forma speciale. Ad esempio, date tre soluzioni a un circuito a 2 sacchetti, la loro mediana bit è anche una soluzione. Allo stesso modo, date tre soluzioni a un circuito XOR-SAT, anche la loro XOR è una soluzione. Infine, date due soluzioni a un circuito di corno, il loro bit ed è anche una soluzione.
Esiste una situazione simile per 3-Sat, in cui dato alcuni sottoinsieme di soluzioni, si possono in qualche modo generare soluzioni aggiuntive?
In caso contrario, esiste un problema SAT correlato a cui può essere ridotto 3-Sat, e quindi che è anche NP-completo, che hanno soluzioni del modulo specificato? Ad esempio 1 in 3 sab, o esattamente-3-sat o nae-3-sat o ecc.
Nessuna soluzione corretta