Base mínima para conjunto de vetores binários usando XOR

8

Eu ficaria surpreso se esse não fosse um problema bem estudado, mas não tenho certeza do que mais procurar nesse momento: você recebe um conjunto de códigos binários. n-vetores S{0,1}n. O problema é encontrar outro conjunto de bináriosn-vetores B{0,1}n, com tamanho mínimo |B|, de modo que todo vetor em S pode ser expresso pelos resultados XOR de algum subconjunto de B (tão B é essencialmente uma base para S usando XOR em vez de adição e permitindo apenas coeficientes binários na combinação linear).

De certa forma, essa é uma forma de PCA para vetores binários. Enquanto procurava literatura sobre esse problema, deparei-me com o Problema de Base Discreta, também discutido nesta tese de doutorado , que parece intimamente relacionada. Em vez de XOR, ele usa OR e aqui|B| é uma entrada adicional (e a tarefa é minimizar o erro na representação S com vetores de B) Este problema é NP-difícil. O mesmo se aplica ao problema que apresentei acima ou existe uma solução eficiente? Qualquer indicação para a literatura existente seria muito apreciada.

Martin Ender
fonte

Respostas:

11

Se você tratar seus vetores como sobre o campo GF(2) ao invés do conjunto {0,1}, o que você pede é encontrar uma base para o período de um conjunto de vetores. Este é um problema bem estudado em álgebra linear, para o qual você provavelmente conhece a solução. (Uma opção é a eliminação gaussiana.)

Yuval Filmus
fonte
Essa é uma ótima oportunidade para aprimorar sua álgebra linear.
Yuval Filmus
Obrigado por me fazer facepalm muito difícil. Agora é realmente óbvio ...;) #
277 Martin Ender