(0,1) -Vektor-XOR-Problem

8

Dies ist eine Neufassung einer anderen meiner jüngsten Fragen [1], die nicht gut formuliert wurde (sie hatte eine halb offensichtliche Vereinfachung, mea culpa), aber ich denke, es gibt immer noch eine nicht triviale Frage im Kern. habe ähnliche Probleme in der Literatur gesehen, aber nicht dieses im Besonderen.

Ich werde es in Bitvektoren schreiben, weil das für mich am einfachsten ist.

es gebe einen Satz von Bitvektoren der Größe , . Betrachten Sie die bitweise XOR-Operation. gegeben ein Zielvektor . Finden Sie eine Teilmenge von Vektoren, so dass das bitweise XOR der Menge gleich dem Zielvektor ist. Was ist ein effizienter (oder idealerweise optimaler) Algorithmus, um eine Teilmenge zu finden? $n$ $v_1, v_2, v_3, ... , v_n$ $v_0$

Der Brute-Force-Algorithmus zählt die Potenzmenge der Größe und listet die erste gefundene Teilmenge auf. (etwas?) effizienter würde 1-Positionen im Ziel betrachten und Teilmengen ausschließen, die nicht mindestens 1 Vektor mit einer 1 in einer 1-Position des Ziels haben. $2^n$

Die Teilmenge kann existieren oder nicht. es kann eindeutig sein oder nicht.

eng verwandte Fragen: (1) Finden der kleinsten Teilmenge, (2) Ausgabe von T / F in Abhängigkeit davon, ob eine solche Teilmenge existiert.

Ich habe den Verdacht, dass eines dieser Probleme NP vollständig ist.

Auf der Suche nach Referenzen, Einsichten usw. wäre es interessant zu wissen, ob es "harte" oder "einfache" Eingaben usw. gibt

Wie ich auf der anderen Frage schrieb, scheint dies eng mit dem Teilmengen-Summenproblem (siehe z. B. garey & johnson ref) verbunden zu sein, von dem bekannt ist, dass es NP-vollständig ist, aber dies scheint "etwas" weniger komplex zu sein, da es einfacher ist, einen Vektor bitweise XOR zu berechnen als eine binäre Summe (die Summe kann mehr binäre Ziffern haben).

Das Problem scheint auch eng mit der jüngsten Frage von bin fu verbunden zu sein [2].

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

[2] Algorithmisches Vektorproblem

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

2

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

$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)$

$\oplus L$ $\text{NC}^2 \subseteq \text{P}$

$\oplus L$

Michael Blondin
quelle

12

Als Folge meines Kommentars: Das Finden der kleinsten befriedigenden Teilmenge sollte tatsächlich NP-vollständig sein; Die Reduzierung erfolgt auf das Codeproblem mit minimalem Gewicht (auf der Grundlage eines Codes über GF (2), wie lautet der Vektor mit minimalem Gewicht im Code?), und dies wurde anscheinend 1997 von A. Vardy als NP-vollständig erwiesen: " Die Unlösbarkeit der Berechnung des Mindestabstands eines Codes ", http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542

Steven Stadnicki
quelle

Wenn ich mich recht erinnere, verwendet Vardy eine Reduktion des Problems der minimalen Teilmengen-Summe über endliche Felder der Eigenschaft 2, die als NP-vollständig bekannt ist und tatsächlich den Anforderungen von OP entspricht.

Mahdi Cheraghchi

1

Gibt es ein Näherungsergebnis für dieses Problem?

Bin Fu

@bin ist gerade auf diesen Ref gestoßen, der Approximationsvarianten berücksichtigt. Eine deterministische Reduzierung für das Gap-Minimum-Distance-Problem Cheng / Wan & zitiert andere Refs, die hilfreich sein

könnten

(0,1) -Vektor-XOR-Problem

Antworten: