Unico 1-in-3 seduto

Question

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

Conosco il valore di ogni bit del compito unico perché è stato realizzato da un circuito di moltiplicazione binaria in cui mi moltiplicato due numeri PREMS 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 di A e B nell'ordine corretto nei bit di ingresso.

Il numero di veri letterali in ciascuna clausola è 1, 2 o 3. Perché conosco il valore di ogni bit, posso dire esattamente quali letterali sono vere in ogni clausola e conta loro. Ad esempio, so quali clausole sono soddisfatte esattamente da 1 letterale. E quel letterale è logicamente parte della soluzione unica.

La mia domanda è semplice: se rimuovo tutte le clausole con più di 1 vero letterale, il compito sarà necessariamente unico?

In altre parole, se volessi scrivere una prova di risoluzione (probabilmente esponenzialmente a lungo) per dimostrare che la soluzione è unica (un altro problema di soluzione, in co-np), posso scriverlo usando solo le clausole con 1 vero letterale?

Intuitivamente, penso così, ma non sono in grado di difendere il mio punto di vista, anche quando pensi al 2sat equivalente.

Answer 1

Considera il seguente CNF: $$ (A \ Lor \ lnot b) \ Land (\ lnot a \ lor b) \ atterra (a \ lor b). $$ Ha un compito soddisfacente unico, $ a= b=top $ , che soddisfa l'ultima clausola due volte.Tuttavia, se si rimuove l'ultima clausola, si ottiene un altro assegno soddisfacente, $ a= b=bot $ .