Algoritmo para álgebra idempotente

Question

Uma expressão de álgebra booleana pode ser convertida em uma álgebra idempotente usando$$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$

onde $\ovezes$ é o produto idempotente (sem potências).Por exemplo, $$(a+b)\otimes(a-b) = a -ab +ab - b = a-b.$$

A fórmula 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)$$

pode ser convertido no que eu chamaria de expressão idempotente$$\phi = (a + b - ab)\otimes (b-bc) \otimes (a+c-2ac).$$

Esta expressão se expande para dar $\phi = ab - abc$.Eu gostaria de um algoritmo que, dada uma fórmula CNF como entrada, produzisse o termo com a menor homogeneidade.Neste exemplo, o oráculo retornaria $ab$.(Se houver vários termos, todos com homogeneidade mínima, o algoritmo poderá retornar qualquer um deles.)

Questão 1:Qual é a complexidade desta tarefa?Quão alto está na hierarquia polinomial?

Em segundo lugar, dada uma expressão idempotente diferente $$\phi = ac+ad+bc+bd-abc-abd-2acd-2bcd + 2abcd,$$

Estou interessado em somar os termos com igual homogeneidade.Deixando todas as variáveis ​​serem $\épsilon$ Nós temos$$\phi = 4\épsilon ^2 - 6\épsilon^3 + 2\épsilon^4.$$Isso produz um vetor de homogeneidade de $[0,0,4,-6,2]$.

Questão 2:Qual é a complexidade de calcular o vetor de homogeneidade, dada uma expressão idempotente como entrada?Quão alto está na hierarquia polinomial?

Answer 1

Vamos considerar a seguinte versão de decisão do seu primeiro problema:

Dada uma instância SAT, sua representação multilinear tem no máximo um termo de grau? $d$?

Afirmo que este é o caso se a instância SAT tiver uma atribuição satisfatória com no máximo $d$ uns.

Na verdade, suponha primeiro que $m$ é um termo de inclusão mínima na representação multilinear da instância.Substituindo 1 pelas variáveis ​​em $m$ e 0 para as variáveis ​​fora de $m$, obtemos 1, ou seja, que a instância está satisfeita.Isto mostra que se a representação multilinear tiver um termo de grau no máximo $d$, então a instância tem uma atribuição satisfatória com no máximo $d$ uns.

Agora suponha que todos os termos na representação multilinear tenham grau maior que $d$.Se substituirmos qualquer atribuição por no máximo $d$ uns, então todos os monômios são iguais a 0 e, portanto, a atribuição falsifica a instância.

Portanto a versão de decisão é equivalente a MIN-ONES-SAT, que é o seguinte problema:

Dada uma instância SAT, ela tem uma atribuição satisfatória com no máximo $d$ uns?

O problema está em NP (é fácil contar o número de unidades em uma tarefa satisfatória) e é claramente NP-difícil (considere $d=n$).Portanto, o problema é NP-completo.

---

Usando um oráculo NP, podemos facilmente encontrar um monômio com grau mínimo, equivalentemente, uma atribuição satisfatória com os mínimos.Basta substituir um 0 em uma das variáveis ​​e ver se aumenta o peso mínimo de uma solução.Nesse caso, defina esta variável como 1, caso contrário, defina-a como zero e continue para a próxima variável.Isso responde à sua primeira pergunta.