Ist das Problem „Wenig diskriminierende Bits“ NP-vollständig?

Das ist ein Name, den ich mir für dieses Problem ausgedacht habe. Ich habe es noch nirgends zuvor beschrieben gesehen. Ich habe noch keinen Beweis für die NP-Vollständigkeit oder einen polynomialen Zeitalgorithmus für dieses Problem finden können. Es ist kein Problem mit den Hausaufgaben - es hängt mit einem Problem zusammen, auf das ich bei meiner Arbeit gestoßen bin.

WENIGE DISKRIMINIERENDE BITS

INSTANZ: Eine Menge T, die Bitvektoren enthält, wobei jeder Bitvektor genau N Bits lang ist. Jedes Element von T ist einzigartig, wie man es von einer Menge in Mathematik erwarten würde. Eine ganze Zahl K <N.

FRAGE: Gibt es eine Menge B von höchstens K Bitpositionen (dh ganze Zahlen im Bereich [0, N-1]), so dass, wenn wir alle Bits mit Ausnahme derjenigen in B von jedem Vektor in T entfernen, die verbleibenden kürzeren Vektoren alle sind immer noch einzigartig?

Beispiel 1: Für die Instanz N = 5, T = {00010, 11010, 01101, 00011}, K = 2 lautet die Antwort Ja, da wir die Bitpositionen B = {0,3} auswählen können. Unter Verwendung der Konvention, dass die Bitposition 0 ganz rechts ist und die Bitpositionsnummern von rechts nach links zunehmen, werden alle Bitpositionen mit Ausnahme derjenigen in B aus den Vektoren in T entfernt. und das sind alle einzigartig.

Beispiel 2: N = 5, T = {00000, 00001, 00010, 00100}, K = 2. Die Antwort ist nein, da unabhängig davon, welche zwei Bitpositionen wir auswählen, keiner der 2-Bit-Vektoren gleich 11 ist, so dass mindestens zwei der 2-Bit-Vektoren einander gleich sind.

Wir können dieses Problem natürlich lösen, indem wir alle (N wähle K) Teilmengen mit der Größe K der N Bitpositionen aufzählen und bestimmen, welche die Bedingung der Frage erfüllen. Dies ist jedoch in der Eingabegröße exponentiell.

Dieses Problem ist NP-vollständig. Ein auf der Reduktion von 3-SAT basierender Beweis lautet wie folgt:

Stellen Sie sich eine Instanz von 3-SAT mit Variablen und Klauseln vor. Wir werden Bitvektoren ("Zeilen") mit der Länge , so dass die kleinste Anzahl von Unterscheidungsbits iff die ursprüngliche 3-SAT-Instanz ist erfüllbar.m 2 n + 2 m 2 n + ⌈ log 2 ( n + m ) ⌉ n + ⌈ log 2 ( n + m ) $n$$m$$2n + 2m$$2n + \lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$

Die ersten Bits entsprechen den Literalen . Im Hinblick auf diese Bits sind die ersten werden Reihen paarweise kommen, von denen die erste eine haben für jedes Literal in dem entsprechenden Abschnitt enthalten, und von denen die zweite wird vollständig aus bestehen ist. Die verbleibenden Reihen kommen ebenfalls in Paaren, von denen die erste haben 's für die entsprechenden literalen und dessen Negation und die zweite von der vollständig aus bestehen ist. Schließlich das letzte{ x 1 , ¬ x 1 , x 2 , ¬ x 2 , . . . , x n , ¬ x n } 2 m 1 0 2 n 1 0 ⌈ log 2 ( n + m ) $2n$$\left\{ x_1, \neg x_1, x_2, \neg x_2, ..., x_n, \neg x_n \right\}$$2m$$1$$0$$2n$$1$$0$$\lceil \log_2(n + m) \rceil$Bits werden verwendet, um jedes Zeilenpaar mit seinem Index von bis , der binär geschrieben ist, zu "signieren" .$0$$n+m-1$

Um jede "Literal" -Zeile von ihrem Nachfolger zu unterscheiden, muss entweder das diesem Literal entsprechende Bit oder das seiner Negation entsprechende Bit beibehalten werden. Um zwischen den "Null + Index" , müssen auch alle beibehalten werden. Die minimal mögliche Anzahl von Unterscheidungsbits ist daher . Um schließlich jede "Klausel" -Zeile von ihrem Nachfolger zu unterscheiden, muss mindestens eines der drei Bits beibehalten werden, die den in dieser Klausel enthaltenen Literalen entsprechen. Wenn die 3-SAT-Instanz erfüllt werden kann, erfordert diese letzte Bedingung keine zusätzlichen Bits (insbesondere$n+m$$\lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$$x_i$$\neg x_i$ für irgendeinen ); und umgekehrt, wenn es Bits gibt, die zwischen allen Bitvektoren unterscheiden, müssen sie genau eines von und für jedes und daher a entsprechen befriedigende Zuordnung von Wahrheitswerten zu den Variablen.$i$$n + \lceil \log_2(n + m) \rceil$$2n+2m$$x_i$$\neg x_i$$i$$n$

Obwohl bereits ein Nachweis der NP-Vollständigkeit erbracht wurde, sollte darauf hingewiesen werden, dass dieses Problem einem bekannten NP-vollständigen Problem entspricht, das als Minimum Test Set Problem ([SP6] in Garey und Johnson , auch als Minimum Test Collection bezeichnet) bezeichnet wird problem ): tauschen sie einfach die rolle der sets und die rolle der positionen aus.