O XOR-SAT NP é pesado?

7

Dado n variáveis ​​booleanas x1,,xn cada um dos quais recebe um custo positivo c1,,cnZ>0 e uma função booleana f nessas variáveis ​​dadas na forma

f(x1,,xn)=i=1kj=1lixrij
( denotando XOR) com kZ>0inteiros 1lin e 1ri1<<rilin para todos i=1,,k, j=1,,li, o problema é encontrar uma atribuição de custo mínimo para x1,,xn isso satisfaz f, se essa atribuição existir. O custo de uma tarefa é simplesmente dado por
i{1,,n}xitrueci.
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 F2(consulte, por exemplo, https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#XOR-satisfiability ). O resultado desta solução (se existir) é um subespaço afim deF2n. 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, reescreverf em binário k×n-matrix, com um 1 para cada xrij no i-a linha e o rij-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 x1,,xn 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?
Alexander Klauer
fonte

Respostas:

9

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 matrizA e um vetor b sobre F2e 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 sistemaAx=b é equivalente à conjunção de equações da forma xi1xim=β. E seβ=1, essa equação já está na forma correta. E seβ=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 x1 tem peso 1. Chegamos agora a uma formulação equivalente de decodificação de máxima probabilidade, que é uma instância do seu problema.

Yuval Filmus
fonte