Algoritmo per l'algebra Idempotente

Question

Un'espressione di algebra booleana può essere convertita in un'algebra idempotente usando $$ \ BAR A \ Equiv 1-A, \ QQual A \ Vee B \ Equiv A + B -Ab, \ Qquad A \ Wedge B \ Equiv A \ Otimes B $$ < / span>

Dove $ \ otimes $ è il prodotto idonento (senza poteri). Ad esempio, $$ (A + B) \ Otimes (A-B)= A -AB + AB-B= A-B. $$

La formula CNF

$$ \ phi= (a \ vee b) \; (b \ vee c) (b \ vee \ bar c) (\ bar b \ vee \ bar c) \; (A \ Vee c) (\ bar A \ Vee \ bar c) $$

può essere convertito in quello che chiamerei l'espressione idonessiva $$ \ PHI= (A + B - AB) \ Otimes (B-BC) \ Otimes (A + C-2AC). $$

Questa espressione si espande per dare $ \ phi= ab - ABC $ . Vorrei un algoritmo che, date una formula CNF come input, emette il termine con l'omogeneità più bassa. In questo esempio, l'Oracle ritornerebbe $ AB $ . (Se ci sono molteplici termini con omogeneità minima, l'algoritmo può restituire uno di essi.)

Domanda 1: qual è la complessità di questo compito? Quanto è alto nella gerarchia polinomiale?

secondariamente, data una diversa espressione idempotente $$ \ phi= AC + AD + BC + BD-ABC-ABD-2ACD-2BCD + 2ABCD, $$ < / P >.

Sono interessato a riassumere i termini con uguale omogeneità. Lasciando che tutte le variabili sia $ \ epsilon $ otteniamo $$ \ PHI= 4 \ Epsilon ^ 2 - 6 \ Epsilon ^ 3 + 2 \ Epsilon ^ 4. $$ Ciò produce un vettore di omogeneità di $ [0,0,4, -6,2] $ .

Domanda 2: Qual è la complessità del calcolo del vettore di omogeneità, data un'espressione idempotente come input? Quanto è alto nella gerarchia polinomiale?

Answer 1

Consideriamo la seguente versione decisionale del tuo primo problema:

.

Dato un istanza SAT, la sua rappresentazione multilinea ha un termine di grado al massimo $ d $ ?

Afferlo che questo è il caso dell'istituzione SAT l'istanza SAT ha un incarico soddisfacente con la maggior parte dei $ D $

Infatti, supponiamo prima che $ m $ è un termine minimo di inclusione nella rappresentazione multilineata dell'istanza. Sostituzione 1 per le variabili in $ m $ e 0 per le variabili al di fuori di $ m $ , otteniamo 1, cioè, che l'istanza è soddisfatta. Ciò dimostra che se la rappresentazione multilinea ha un termine di grado al massimo $ d $ , quindi l'istanza ha un incarico soddisfacente con la maggior parte dei contenitori di matematica $ D $ quelli.

Ora supponiamo che tutti i termini della rappresentazione multilinea abbiano laurea in più di $ d $ . Se sostituiamo qualsiasi incarico con la maggior parte dei $ d $ quelli, quindi tutti i monomiali uguali 0, e quindi l'assegnazione falsifica l'istanza.

Pertanto la versione decisionale è equivalente a min-one-sat, che è il seguente problema:

.

Dato un'istanza SAT, ha un compito soddisfacente con la maggior parte dei $ d $ quelli?

Il problema è in NP (è facile contare il numero di quelli in un incarico soddisfacente) ed è chiaramente NP-HARD (Take $ D= N $ ). Quindi il problema è NP-Complete.

---

.

Usando un NP Oracle, possiamo facilmente trovare un monomiale con grado minimo, equivalentemente, un incarico soddisfacente con i meno. Basta sostituire un 0 in una delle variabili e vedere se aumenta il peso minimo di una soluzione. In tal caso, impostare questa variabile su 1, altrimenti impostarlo su zero e continuare alla variabile successiva. Questo risponde alla tua prima domanda.