esta é uma reescrita de outra questão recente [1] que não foi bem estabelecida (tinha uma simplificação semi-óbvia, mea culpa), mas acho que ainda há uma questão não trivial no centro. vi problemas semelhantes na literatura, mas não esse em particular.
escreverei em termos de vetores de bits, porque é mais fácil para mim.
que haja um conjunto de bits-vectores de tamanho , v 1 , v 2 , v 3 , . . . , v n . considere a operação XOR bit a bit. dado um vetor de destino v 0 . encontre um subconjunto de vetores de forma que o XOR bit a bit do conjunto seja igual ao vetor de destino. o que é um algoritmo eficiente (ou idealmente, ideal) para encontrar um subconjunto?
o algoritmo de força bruta enumera o conjunto de potência de tamanho e lista o primeiro subconjunto encontrado. (ligeiramente?) mais eficiente analisaria as posições 1 no destino e excluiria subconjuntos que não possuem pelo menos 1 vetor com 1 na posição 1 do destino.
o subconjunto pode ou não existir. pode ou não ser único.
questões estreitamente relacionadas: (1) encontre o menor subconjunto, (2) produza T / F dependendo da existência desse subconjunto.
suspeite que um desses problemas é NP completo.
procurando referências, insight etc., seria interessante saber se existem entradas "difíceis" vs "fáceis" etc.
como escrevi na outra pergunta, isso parece intimamente relacionado ao problema da soma do subconjunto (veja, por exemplo, garey & johnson ref), que é conhecido por ser NP completo, mas isso parece ter "um pouco" menos complexidade, porque é mais fácil calcular um vetor XOR bit a bit do que uma soma binária (a soma pode ter mais dígitos binários).
o problema também parece estar intimamente ligado à recente pergunta de bin fu [2]
Respostas:
Seja . O problema é determinar se o seguinte sistema possui uma solução:v0 0, v1, … , Vn∈ Zm2
fonte
Como acompanhamento do meu comentário: encontrar o menor subconjunto satisfatório deve ser de fato NP-completo; a redução está no problema do código de peso mínimo (dada a base para um código acima de GF (2), qual é o vetor de peso mínimo no código?) e isso aparentemente foi comprovado como NP-completo em 1997 por A. Vardy: " A intratabilidade de calcular a distância mínima de um código ", http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542
fonte