Czy problem „najmniejszej liczby bitów dyskryminujących” jest NP-zakończony?

To nazwa, którą wymyśliłem dla tego problemu. Nigdzie go nie widziałem. Nie udało mi się znaleźć dowodu kompletności NP ani algorytmu wielomianowego czasu dla tego problemu. To nie jest zadanie domowe - jest związane z problemem, z którym się spotkałem w swojej pracy.

NAJNOWSZE BITKI DYSKRYMINUJĄCE

INSTANCJA: Zestaw T zawierający wektory bitowe, gdzie każdy wektor bitowy ma dokładnie N bitów długości. Każdy element T jest unikalny, jak można się spodziewać po zbiorze matematycznym. Liczba całkowita K <N.

PYTANIE: Czy istnieje zestaw B co najwyżej pozycji K bitów (tj. Liczb całkowitych z zakresu [0, N-1]) tak, że gdy usuwamy wszystkie bity oprócz tych w B z każdego wektora w T, wszystkie pozostałe wektory krótsze są wszystkie nadal wyjątkowy?

Przykład 1: Dla instancji N = 5, T = {00010, 11010, 01101, 00011}, K = 2, odpowiedź brzmi tak, ponieważ możemy wybrać pozycje bitów B = {0,3}. Stosując konwencję, pozycja bitu 0 jest skrajnie prawostronna, a numery pozycji bitów rosną od prawej do lewej, usuwając wszystkie pozycje bitów oprócz tych w B z wektorów w T pozostawiając T '= {00, 10, 11, 01}, i wszystkie są wyjątkowe.

Przykład 2: N = 5, T = {00000, 00001, 00010, 00100}, K = 2. Odpowiedź brzmi nie, ponieważ bez względu na to, które dwie wybrane przez nas pozycje bitów, żaden z 2-bitowych wektorów nie będzie równy 11, więc co najmniej dwa z 2-bitowych wektorów będą sobie równe.

Możemy oczywiście rozwiązać ten problem, wyliczając wszystkie podzbiory (N wybieram K) o rozmiarze K pozycji N bitów i określając, które spełniają warunek pytania. Jest to jednak wykładnicze w wielkości wejściowej.

Ten problem jest NP-zupełny. Dowód oparty na redukcji z 3-SAT jest następujący:

$n$$m$$2n + 2m$$2n + \lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$

$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$$0$$n+m-1$

$n+m$$\lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$$x_i$$\neg x_i$$i$$n + \lceil \log_2(n + m) \rceil$$2n+2m$$x_i$$\neg x_i$$i$$n$

Chociaż dostarczono już dowód kompletności NP , warto wskazać, że problem ten jest równoważny ze znanym problemem NP-kompletnym, zwanym problemem minimalnego zestawu testów ([SP6] w Garey i Johnson , zwanym również zbiorem testów minimalnych problem ): wystarczy wymienić rolę zbiorów i rolę pozycji.