(0,1) - masalah vektor XOR

8

ini adalah penulisan ulang pertanyaan saya yang lain baru-baru ini [1] yang tidak dinyatakan dengan baik (memiliki penyederhanaan yang jelas, mea culpa) tapi saya pikir masih ada pertanyaan yang tidak penting di jantungnya. telah melihat masalah serupa dalam literatur tetapi tidak yang satu ini pada khususnya.

akan menulisnya dalam bentuk bit-vektor karena itu yang paling mudah bagi saya.

biarkan ada satu set bit-vektor ukuran , . pertimbangkan operasi XOR bitwise. diberi vektor target . menemukan subset vektor sedemikian rupa sehingga XOR bitwise dari himpunan sama dengan vektor target. apa itu algoritma yang efisien (atau idealnya, optimal) untuk menemukan subset? $n$ $v_1, v_2, v_3, ... , v_n$ $v_0$

Algoritma brute force menyebutkan Power Set ukuran $2^n$ dan daftar subset 1 ditemukan. (Sedikit?) Lebih efisien akan melihat 1-posisi di target dan mengecualikan himpunan bagian yang tidak memiliki setidaknya 1 vektor dengan 1 di posisi 1-target.

bagian mungkin atau tidak ada. mungkin unik atau tidak.

pertanyaan terkait erat: (1) menemukan subset terkecil, (2) output T / F tergantung pada apakah ada subset tersebut.

memiliki kecurigaan salah satu dari masalah ini adalah NP lengkap.

mencari referensi, wawasan dll. akan menarik untuk mengetahui apakah ada input "sulit" vs "mudah" dll

seperti yang saya tulis pada pertanyaan lain ini tampaknya berkaitan erat dengan masalah jumlah himpunan bagian (lihat misalnya garey & johnson ref) yang dikenal sebagai NP lengkap tetapi ini tampaknya memiliki "sedikit" kompleksitas kurang karena lebih mudah untuk menghitung bitwise vektor XOR dari jumlah biner (jumlahnya dapat memiliki lebih banyak digit biner).

masalahnya juga tampaknya terkait erat dengan pertanyaan terakhir bin fu [2]

[1] /cstheory/10341/building-0-1-vectors-out-of-xors

[2] Masalah Vektor Algoritma

cc.complexity-theory reference-request circuit-complexity lower-bounds vzn
sumber

2

Masalah ini persis pertanyaan 'apakah vektor dalam rentang vektor modulo 2?'; jika adalah mod 2 yang bebas linear maka semua adalah dan masalahnya dapat diselesaikan dengan inversi matriks; dan bahkan jika tidak independen itu harus mudah dipecahkan melalui eliminasi gaussian. Masalah 'subset memuaskan terkecil' mungkin NP-lengkap - itu pada dasarnya bertanya 'apa vektor bukan nol berat terkecil dalam rentang vektor modulo 2 ini?' - tapi saya belum cukup sadar untuk memiliki jawaban yang tepat untuk itu.

v_{0}

$v_0$

v_{1} . . v_{n}

$v_1..v_n$

v_{i}

$v_i$

v_{0}

$v_0$

v_{i}

$v_i$

Steven Stadnicki

17

Biarkan . Masalahnya adalah untuk menentukan apakah sistem berikut memiliki solusi: $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$

(\begin{matrix} v_{1} & \dots & v_{n} \end{matrix}) (\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}) = v_{0} (mod 2)

$\begin{pmatrix} v_1 & \cdots & v_n \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = v_0 \, (\text{mod } 2)$

Masalah ini dikenal sebagai -complete oleh [Damm90, BDHM92], dengan demikian di dalam . $\oplus L$ $\text{NC}^2 \subseteq \text{P}$

[Damm90] Carsten Damm: Masalah lengkap untuk . Inf. Proses. Lett. 36 (5): 247-250 (1990) [BDHM92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Struktur dan Pentingnya Kelas Logspace-MOD. Teori Sistem Matematika 25 (3): 223-237 (1992) $\oplus L$

Michael Blondin
sumber

12

Sebagai tindak lanjut dari komentar saya: menemukan subset terkecil yang memuaskan sebenarnya harus NP-lengkap; pengurangannya adalah pada masalah kode bobot minimum (diberikan dasar untuk kode lebih dari GF (2), apa vektor bobot minimum dalam kode?) dan ini terbukti telah selesai NP pada tahun 1997 oleh A. Vardy: " Ketidakstabilan menghitung jarak minimum kode ", http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542

Steven Stadnicki
sumber

Jika saya ingat benar, Vardy menggunakan pengurangan dari masalah subset-sum minimum atas bidang hingga karakteristik 2, yang dikenal sebagai NP-complete dan memang setara dengan apa yang diminta OP.

Mahdi Cheraghchi

1

Apakah ada hasil perkiraan untuk masalah ini?

Bin Fu

@bin hanya berlari melintasi ref ini yang mempertimbangkan varian aproksimasi A Reduksi deterministik untuk Kesenjangan Jarak Minimum Masalah Cheng / Wan & mengutip referensi lain yang mungkin membantu

vzn

(0,1) - masalah vektor XOR

Jawaban: