Unico 3sat a 1-in-3sat unico

Question

Supponiamo di avere una formula CNF con clausole di dimensioni 2 e 3. Ha un compito soddisfacente unico.

È stato realizzato da un circuito di moltiplicazione binaria in cui molti PRIMATICI DUE PREMES Numeri A e B in modo tale che A * B= S dove sia un numero semiprima. Ho aggiunto le condizioni che a!= 1, b!= 1 e A <= B, quindi ha aggiunto il valore della S alla formula Assicurarsi che l'assegnazione sia univocata. L'unico modo per soddisfare la formula è mettere i valori delle prime A e B nell'ordine corretto nei bit di ingresso.

In 1-in-3sat, costringiamo che esattamente 1 letterale dovrebbe essere vero in ciascuna tripletta e altri due falsi. Se esattamente 2 letterali sono vere, possiamo capovolgere tutti gli iterali nella clausola per ottenere una clausola equivalente 1-in-3sat (in altre parole 2-in-3sat è lo stesso problema).

Osservazione di base: mentre una normale o clausola elimina 1 possibilità su 8, una clausola 1-in-3 elimina 5 possibilità su 8.

3sat può essere ridotto a 1-in-3 SAT, tale che se la formula 3sat è soddisfatta quindi è la formula ridotta.

Tuttavia, le riduzioni non sembrano preservare il numero di incarichi, introducendo nuove variabili senza forzare il loro valore.

può essere unico 3sat essere ridotto in unica 1-in-3sat ...

.
1. senza conoscere l'assegnazione corretta?
2. In caso contrario, mentre sapendo l'assegnazione corretta?

Answer 1

Sì, una formula a 3 satelliti $ \ phi $ può essere trasformato in una formula 1-in-3 formula $ \ phi '$ preservando il numero di incarichi soddisfacenti. Per evitare ambiguità utilizzerò " $ \ Vee $ " tra i letterali di una clausola 3 satellitare e virgole tra letterali di una clausola 1-in-3 satellitare. < / P >.

---

.

Lasciami vedere preliminariamente che, dato due lettedri $ A $ e $ B $ , possiamo Simula un nuovo tipo di clausola $ (x= a \ wedge b) $ che costringe il valore di una nuova variabile $ x $ per essere $ a \ wedge B $ usando solo vincoli SAT 1-in-3, senza introdurre una nuova soluzione.

Considera le cluasi: $$ (\ overline {b}, c, x) \ cuneo (a, c, d) \ cuneo (\ Overline {A}, E, X) \ Wedge (B, E, F) $$

Se $ a=top $ e $ B=Top $ , quindi il 2 ° e la 4a clausole garantisce che $ c= d= e= f=bot $ . Le prime e terze clausole assicurano quindi che $ x=top $ .

Se $ a=top $ e $ B=Bot $ , quindi il 2 ° La clausola garantisce che $ c= d=bot $ . La prima clausola garantisce quindi che $ x=bot $ . La 3rd clausola garantisce che $ e=top $ e la quarta clausola implica $ f=Bot $ .

La cassa $ a=bot $ e $ B=Top $ è simmetrico.

se $ a=bot $ e $ B=Bot $ , quindi il 1 ° e 3 ° clausato Implica $ c= E= x=Bot $ . Le 2 e quarta clausole assicurano $ d= f=top $ .

---

.

Sono ora pronto per trasformare una formula $ \ phi $ di 3sat in una formula $ \ PHI '$ < / span> di 1-in-3 seduto. Considera ora una clausola $ (a \ vee b \ vee c) $ di $ \ phi $ . Questo può essere trasformato nelle seguenti clausole Equivalenti 1-in-3 SAT:

.

• Aggiungi una nuova variabile $ x $ Vera IFF $ A $ è falso e $ B $ è vero. Questo è codificato dalla clausola $ (x=overline {a} \ wedge b) $ .

• Aggiungi una nuova variabile $ y $ che è vero IFF $ A $ è falso , $ B $ è falso, e $ c $ è vero. Avremo bisogno di una variabile aggiuntiva $ z $ . La clausola $ (z=Overline {A} \ Wedge \ Overline {B}) $ assicura che $ z $ < / span> è vero se e solo se $ A $ è falso e $ B $ è falso. Quindi, il valore di $ y $ può essere applicato dalla clausola $ (y= z \ wedge c) $ .

• Se $ (a \ vee b \ vee c) $ è vero quindi almeno una delle $ A $ , $ B $ o $ c $ è vero. Ciò significa che esattamente uno dei $ A $ , $ x $ e $ y $ è vero. Sul Converse, se $ (a \ vee b \ vee c) $ è falso, quindi a tutto $ a $ , $ x $ e $ y $ sono falsi. Questo mostra che $ (a \ vee b \ vee c) $ è soddisfacente se e solo se $ (A, X, y $ ) è soddisfacente.

Abbiamo quindi costruito una formula di una formula di 1-in-3 equivalente $ \ phi '$ che utilizza una superset delle variabili della formula originale di 3 satelliti < class="Math-Container"> $ \ PHI $ . Un incarico di verità alle variabili di $ \ phi '$ soddisfa $ \ phi' $ se e solo se L'assegnazione limitata alle variabili di $ \ phi $ soddisfa $ \ phi $ . Pertanto, se una nuova soluzione a $ \ phi '$ è introdotto, deve essere dovuto alle variabili di nuova aggiunta $ x $

n>, $ y $ e $ z $ (un set per ogni clausola).Tuttavia, i valori di queste variabili sono completamente determinati dai valori delle variabili di $ \ phi $ .

Answer 2

Tale riduzione è descritta nell'appendice B di Régis Barbanchon, sul grafico unico 3-Colorabilità e riduzioni parsimoniose nel piano .Barbanchon lo attribuisce al lavoro precedente ([9] nella bibliografia).Altrove, ho visto un'attribuzione alla celebrata carta di Schaefer in cui dimostra il suo famoso teorema di dicotomia, attraverso altrimenti dando una riduzione da 3sat a 1-in-3sat, che è presumibilmente parsimoniosa (non ho controllato).