MIN-2-XOR-SAT e MAX-2-XOR-SAT: são NP-hard?

Qual é a complexidade de e ? Eles estão em P? Eles são NP-difíceis? $\text{MIN-2-XOR-SAT}$ $\text{MAX-2-XOR-SAT}$

Para formalizar isso com mais precisão, vamos

Φ (x) = \land_{i}^{n} C_{i},

$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$

onde $\mathbf{x} = (x_1,\dots,x_m)$ e cada cláusula $C_i$ tem a forma $(x_i \oplus x_j)$ ou $(x_i \oplus \neg x_j)$ .

O problema $\text{2-XOR-SAT}$ é encontrar uma tarefa para $\mathbf{x}$ que satisfaça $\Phi$ . Esse problema está em $P$ , pois corresponde a um sistema de equações lineares mod $2$ .

O problema $\text{MAX-2-XOR-SAT}$ é encontrar uma atribuição para $\mathbf{x}$ que maximize o número de cláusulas que são atendidas. O problema $\text{MIN-2-XOR-SAT}$ é encontrar uma atribuição para $\mathbf{x}$ que minimize o número de cláusulas que são atendidas. Quais são as complexidades desses problemas?

Inspirado em MIN ou MAX-True-2-XOR-SAT NP-hard?

Respostas:

Desculpe por responder uma postagem antiga

O problema de determinar se uma instância de MONOTONE-2-XOR-SAT (todas as cláusulas são do tipo ) é satisfatório pode ser reduzido ao problema de determinar se um gráfico é bipartido, consulte isso . $({x_i}\oplus x_j)$

Para isso, criamos um gráfico com um nó para cada literal da fórmula e conectamos cada literal a outro se eles estiverem na mesma cláusula (arestas são cláusulas) $G$

Por exemplo:

Se tivermos uma fórmula insatisfatória que seja $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4)$

Temos um gráfico como este:

grafo no bipartito

isso não é bipartido

Existem três cláusulas que são satisfatórias e, portanto, temos apenas que eliminar uma vantagem

Agora, podemos reduzir o problema de determinar se podemos encontrar um subgrafo bipartido máximo com vértice para o problema de determinar se podemos satisfazer as cláusulas em uma fórmula MONOTONE-MAX-2XOR-SAT, veja isso . E o problema do subgráfico bipartido máximo é equivalente ao corte máximo $k$ $k$

Para fazer a redução, simplesmente criamos um novo literal para cada vértice e criamos uma cláusula para cada aresta conectando dois literais

Por exemplo:

Nós temos esse gráfico,

grafo no bipartito 2

Criamos a fórmula a seguir $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5)$

Portanto, se pudermos encontrar uma atribuição que satisfaça as cláusulas isso significa que existe um subgrafo bipartido com pelo menos arestas. $k$ $k$

rotia
fonte

Você deve tornar a implicação explícita: Como MAX-CUT é NP-Hard, a redução para MAX-XORSAT significa que também é NP-Hard.

Antimony

-1

Onde cada cláusula é fornecida apenas como , crie um vértice para cada literal , crie uma aresta entre dois vértices se existir um relacionamento XOR entre eles. Para que a declaração seja verdadeira, ela deve satisfazer . Agora podemos adotar o problema de coloração de vértices (não há dois vértices conectados por uma aresta com a mesma cor; só temos 2 cores adicionais se quisermos satisfazer a equação). A cláusula é verdadeira se os vértices correspondentes tiverem atribuído cores diferentes no gráfico. $(x_i\oplus x_j)$ $x_i$ $x_i\oplus x_j$ $x_i\neq x_j$ $x_i\oplus x_j$

Se todos os vértices do gráfico puderem ser coloridos usando duas cores e nenhum dos dois vértices com um compartilhamento de aresta comum tiver a mesma cor, a equação será satisfatória.

Mas um gráfico é bicolor se for um gráfico bipartido. E determinar se um gráfico é bipartido pode ser feito em tempo polinomial. Portanto, o problema está em P, porque, se pudermos determinar em tempo polinomial que o gráfico é bipartido, ele é solucionável, caso contrário, não é solucionável.

jcod0
fonte

Mas a declaração do problema permite ter ambas as cláusulas e . Não vejo como você pretende lidar com cláusulas do segundo tipo. Você está tentando resolver um caso especial em que não há cláusulas do segundo tipo? Algo mais? Talvez você possa recolher / unificar cada par de vértices modo que exista uma cláusula ?

(x_{i} \oplus x_{j})

$(x_i \oplus x_j)$

(x_{k} \oplus \neg x_{l})

$(x_k \oplus \neg x_l)$

k, l

$k,l$

(x_{k} \oplus \neg x_{l})

$(x_k \oplus \neg x_l)$

Isso me leva a um problema mais sério com sua resposta. O problema não é determinar se a fórmula é satisfatória; o problema é identificar uma tarefa que satisfaça o número máximo / mínimo de cláusulas. Seu algoritmo apenas testa se a fórmula é satisfatória. Assim, ele resolve 2-XOR-SAT, mas não resolve MIN-2-XOR-SAT ou MAX-2-XOR-SAT - mas eu já sabia que o 2-XOR-SAT está em P, conforme explicado em a questão. Eu entendi algo errado?

Obrigado, eu fiz a correção, que a minha resposta se aplica somente a cláusula é dada por

x_{i} \oplus x_{k}

$x_i\oplus x_k$

jcod0

Mas ainda não vejo como isso aborda meu segundo comentário. Você resolveu um caso especial de um problema que eu não estava perguntando. Em suma, esta resposta não responde à pergunta que eu fiz.