Le problème «Le moins de bits discriminants» est-il complet?

C'est un nom que j'ai inventé pour ce problème. Je ne l'ai jamais vu décrit auparavant. Je n'ai pas encore trouvé de preuve de complétude NP ni d'algorithme de temps polynomial pour ce problème. Ce n'est pas un problème de devoirs - il est lié à un problème que j'ai rencontré dans mon travail.

MOINS DE DISCRIMINATIONS

INSTANCE: Un ensemble T contenant des vecteurs de bits, où chaque vecteur de bits a exactement N bits de long. Chaque élément de T est unique, comme on pourrait s'y attendre d'un ensemble en mathématiques. Un entier K <N.

QUESTION: Existe-t-il un ensemble B d'au plus K positions de bits (c'est-à-dire des entiers dans la plage [0, N-1]) de telle sorte que lorsque nous supprimons tous les bits sauf ceux de B de chaque vecteur de T, les vecteurs plus courts restants sont tous toujours unique?

Exemple 1: Pour l'instance N = 5, T = {00010, 11010, 01101, 00011}, K = 2, la réponse est oui, car nous pouvons sélectionner les positions de bits B = {0,3}. En utilisant la convention selon laquelle la position de bit 0 est la plus à droite, et les numéros de position de bit augmentent de droite à gauche, supprimant toutes les positions de bit à l'exception de celles de B des vecteurs de T laisse T '= {00, 10, 11, 01}, et ce sont tous uniques.

Exemple 2: N = 5, T = {00000, 00001, 00010, 00100}, K = 2. La réponse est non, car quelles que soient les positions de deux bits que nous sélectionnons, aucun des vecteurs 2 bits ne sera égal à 11, donc au moins deux des vecteurs 2 bits seront égaux entre eux.

Nous pouvons bien sûr résoudre ce problème en énumérant tous (N choisir K) sous-ensembles avec la taille K des N positions de bits, et en déterminant lesquels satisfont la condition de la question. Cependant, c'est exponentiel dans la taille d'entrée.

Ce problème est NP-complet. Une preuve basée sur la réduction de 3-SAT est la suivante:

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

Bien qu'une preuve de la complétude de NP soit déjà fournie, il peut être utile de souligner que ce problème est équivalent à un problème connu de NP-complet appelé le problème de l'ensemble de tests minimum ([SP6] dans Garey et Johnson , également appelé la collection de tests minimum problème ): il suffit d’échanger le rôle des ensembles et le rôle des positions.