Minimale Basis für den Satz von Binärvektoren unter Verwendung von XOR

Ich wäre überrascht, wenn dies kein gut untersuchtes Problem wäre, aber ich bin mir nicht sicher, wonach ich an dieser Stelle noch suchen soll: Sie erhalten eine Menge binärer Vektoren . Das Problem besteht darin, eine andere Menge von binären Vektoren mit minimaler Größe, so dass jeder Vektor in durch die XOR-Ergebnisse einer Teilmenge von ausgedrückt werden kann (also ist im Wesentlichen eine Basis für , die XOR anstelle der Addition verwendet und nur binäre Koeffizienten in der linearen Kombination zulässt).$n$$S \subset \{0,1\}^n$$n$$B \subset \{0,1\}^n$$|B|$$S$$B$$B$$S$

In gewisser Weise ist dies eine Form von PCA für binäre Vektoren. Bei der Suche nach Literatur zu diesem Problem bin ich auf das Problem der diskreten Basis gestoßen, das auch in dieser Doktorarbeit diskutiert wurde und eng verwandt zu sein scheint. Anstelle von XOR wird OR verwendet, und hierist eine zusätzliche Eingabe (und die Aufgabe besteht darin, den Fehler bei der Darstellung von mit Vektoren von zu minimieren ). Dieses Problem ist NP-schwer. Gilt das auch für das oben dargestellte Problem oder gibt es eine effiziente Lösung? Hinweise auf vorhandene Literatur wären sehr willkommen.$|B|$$S$$B$

Wenn Sie Ihre Vektoren eher über dem Feld als über der Menge , müssen Sie eine Grundlage für die Spanne einer Menge von Vektoren finden. Dies ist ein gut untersuchtes Problem in der linearen Algebra, für das Sie wahrscheinlich die Lösung kennen. (Eine Option ist die Gaußsche Eliminierung.)$GF(2)$$\{0,1\}$