Dasar minimal untuk set vektor biner menggunakan XOR

Saya akan terkejut jika ini bukan masalah yang dipelajari dengan baik, tapi saya tidak yakin apa lagi yang harus dicari pada saat ini: Anda diberi satu set biner $n$-Vektor $S \subset \{0,1\}^n$. Masalahnya adalah untuk menemukan satu set biner$n$-Vektor $B \subset \{0,1\}^n$, dengan ukuran minimal $|B|$, sehingga setiap vektor masuk $S$ dapat diekspresikan oleh hasil XOR dari beberapa subset dari $B$ (begitu $B$ pada dasarnya adalah dasar untuk $S$ menggunakan XOR alih-alih penambahan dan hanya memungkinkan koefisien biner dalam kombinasi linear).

Di satu sisi, ini adalah bentuk PCA untuk vektor biner. Saat mencari literatur tentang masalah ini, saya menemukan Masalah Basis Diskrit juga dibahas dalam tesis PhD ini , yang tampaknya terkait erat. Alih-alih XOR menggunakan OR, dan di sini$|B|$ adalah input tambahan (dan tugasnya adalah meminimalkan kesalahan dalam merepresentasikan $S$ dengan vektor dari $B$). Masalah ini NP-hard. Apakah hal yang sama berlaku untuk masalah yang saya sampaikan di atas, atau apakah ada solusi yang efisien? Petunjuk apa pun untuk literatur yang ada akan sangat dihargai.

Jika Anda memperlakukan vektor Anda di atas bidang $GF(2)$ daripada over set $\{0,1\}$, maka yang Anda tanyakan adalah menemukan dasar untuk rentang satu set vektor. Ini adalah masalah yang dipelajari dengan baik dalam aljabar linier, yang mungkin Anda ketahui solusinya. (Salah satu opsi adalah eliminasi Gaussian.)