O XOR-SAT NP é pesado?

Dado $n$ variáveis ​​booleanas $x_1,\ldots,x_n$ cada um dos quais recebe um custo positivo $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ e uma função booleana $f$ nessas variáveis ​​dadas na forma

$$f(x_1,\ldots,x_n)=\bigwedge_{i=1}^k\bigoplus_{j=1}^{l_i}x_{r_{ij}}$$ ($\oplus$ denotando XOR) com $k\in\mathbb{Z}_{>0}$inteiros $1\leq l_i\leq n$ e $1\leq r_{i1}<\cdots<r_{il_i}\leq n$ para todos $i=1,\ldots,k$, $j=1,\ldots,l_i$, o problema é encontrar uma atribuição de custo mínimo para $x_1,\ldots,x_n$ isso satisfaz $f$, se essa atribuição existir. O custo de uma tarefa é simplesmente dado por $$\sum_{\substack{i\in\{1,\ldots,n\}\\x_i\,\text{true}}}c_i.$$ Esse problema é NP-difícil, ou seja, é o problema de decisão que o acompanha "Existe uma atribuição satisfatória de custo no máximo com algum valor $K$"NP-difícil?

Agora, o problema XOR-SAT padrão está em P, pois mapeia diretamente a questão da solvabilidade de um sistema de equações lineares sobre $\mathbb{F}_2$(consulte, por exemplo, https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#XOR-satisfiability ). O resultado desta solução (se existir) é um subespaço afim de$\mathbb{F}_2^n$. O problema é assim reduzido para escolher o elemento correspondente com custo mínimo desse subespaço. Infelizmente, esse subespaço pode ser bastante grande e, de fato, reescrever$f$ em binário $k\times n$-matrix, com um $1$ para cada $x_{r_{ij}}$ no $i$-a linha e o $r_{ij}$-th coluna, e zero caso contrário, temos um problema de minimização de custos sujeito a

$$Ax=1,$$ Onde $A$ é dito matriz, $x$ é o vetor da coluna que consiste no $x_1,\ldots,x_n$ e $1$é o vetor todo-1. Esta é uma instância de um problema de programação linear binária, conhecido como NP-hard em geral. Portanto, a questão é: também é NP-difícil neste caso específico?

Um resultado clássico de Berlekamp, ​​McEliece e van Tilborg mostra que o seguinte problema, decodificação de máxima probabilidade, é NP-completo: dada uma matriz$A$ e um vetor $b$ sobre $\mathbb{F}_2$e um número inteiro $w$, determine se existe uma solução para $Ax = b$ com peso de Hamming no máximo $w$.

Você pode reduzir esse problema ao seu problema. O sistema$Ax = b$ é equivalente à conjunção de equações da forma $x_{i_1} \oplus \cdots \oplus x_{i_m} = \beta$. E se$\beta = 1$, essa equação já está na forma correta. E se$\beta = 0$ então nós XOR uma variável extra $y$ para o lado direito e forçamos essa variável a ser $1$ adicionando uma equação extra $y = 1$. Definimos os pesos da seguinte maneira:$y$ tem peso $0$, e as $x_1$ tem peso $1$. Chegamos agora a uma formulação equivalente de decodificação de máxima probabilidade, que é uma instância do seu problema.